Luokka P

Algoritmien teoriassa luokka P ( englanninkielisestä  polynomista ) on joukko ongelmia, joille on olemassa "nopeita" ratkaisualgoritmeja (jonka ajoaika riippuu polynomiaalisesti syötetyn datan koosta) . P-luokka sisältyy algoritmien laajempiin kompleksisuusluokkiin .

Määritelmät

Muodollinen määritelmä

Algoritmi tunnistetaan deterministisellä Turingin koneella , joka laskee syöttönauhalle annetusta syöttöaakkosesta vastauksen, joka on annettu sanalla . Algoritmin käyntiaika kiinteälle syöttösanalle x on Turingin koneen työjaksojen lukumäärä koneen alusta loppuun. Jonkin Turingin koneen laskeman funktion monimutkaisuus on funktio , joka riippuu syöttösanan pituudesta ja on yhtä suuri kuin koneen maksimikäyttöaika kaikilla kiinteän pituisilla syöttösanoilla:

Jos funktiolle f on olemassa sellainen Turingin kone M , että jollekin luvulle c ja riittävän suuri n , niin sen sanotaan kuuluvan luokkaan P tai on ajallisesti polynomi.

Church-Turingin teesin mukaan mikä tahansa ajateltavissa oleva algoritmi voidaan toteuttaa Turingin koneella. Jokaiselle ohjelmointikielelle voit määrittää luokan P samalla tavalla (korvaamalla Turingin koneen määrittelyssä ohjelmointikielen toteutuksella). Jos sen kielen kääntäjä , jolla algoritmi on toteutettu, hidastaa algoritmin suoritusta polynomiaalisesti (eli algoritmin suoritusaika Turingin koneella on pienempi kuin jokin sen suoritusajan polynomi ohjelmointikielessä), niin luokkien P määritelmät tälle kielelle ja Turingin koneelle ovat samat. Kokoonpanokielikoodi voidaan muuntaa Turingin koneeksi pienellä polynomihidastumisella ja koska kaikki olemassa olevat kielet mahdollistavat kääntämisen kokoonpanoon (jälleen polynomin hidastumisella), luokan P määritelmät Turingin koneille ja kaikille olemassa oleville ohjelmointikielille ovat samat.

Kapeampi määritelmä

Joskus luokka P tarkoittaa kapeampaa funktioiden luokkaa, eli predikaattien luokkaa (funktiot ). Tässä tapauksessa kieli L , jonka tämä predikaatti tunnistaa, on joukko sanoja, joiden predikaatti on yhtä suuri kuin 1. Luokan P kielet ovat kieliä, joille on olemassa luokan predikaatteja. P, jotka tunnistavat ne. On selvää, että jos kielet ja ovat luokassa P, niin niiden liitto, leikkaus ja täydennykset kuuluvat myös luokkaan P.

Luokan P sisällyttäminen muihin luokkiin

Luokka P on yksi kapeimmista monimutkaisuusluokista. Hänelle kuuluvat algoritmit kuuluvat myös luokkaan NP , BPP-luokkaan (koska ne mahdollistavat polynomin toteutuksen nollavirheellä), PSPACE-luokkaan (koska Turingin koneen työalue on aina pienempi kuin aika), P/Poly-luokka (tämän tosiasian todistamiseksi konseptia käytetään koneen protokollaa, joka muunnetaan polynomikoon Boolen malliksi).

Yli 30 vuoden ajan luokkien P ja NP tasa-arvoongelma on ollut ratkaisematta . Jos ne ovat yhtä suuret, mikä tahansa NP-luokan tehtävä voidaan ratkaista nopeasti (polynomiajassa). Tiedeyhteisö on kuitenkin taipuvainen kielteiseen vastaukseen tähän kysymykseen. Lisäksi laajempien luokkien, esimerkiksi PSPACE:n, sisällyttämisen tiukkuutta ei ole todistettu, mutta P:n ja PSPACE:n yhtäläisyys näyttää tällä hetkellä erittäin kyseenalaiselta.

Ongelmaesimerkkejä

Luokkaan P kuuluvat ongelmat

Esimerkkejä luokan P ongelmista ovat kokonaislukujen yhteenlasku, kertolasku, jako, jakolaskun jäännös, matriisikerto , graafien yhteenliittämisen selvittäminen, n luvun joukon lajittelu, Eulerin syklin löytäminen m:n reunan graafista, jonkin verran. sana tekstissä, jonka pituus on n, kattavien vähimmäiskustannuspuiden rakentaminen, lineaarinen ohjelmointi ja joitain muita.

Ongelmat, joiden kuuluminen luokkaan P on tuntematon

On monia ongelmia, joille ei ole löydetty polynomialgoritmia, mutta ei ole todistettu, etteikö sitä ole olemassa. Näin ollen ei tiedetä, kuuluvatko tällaiset ongelmat luokkaan P. Tässä on joitain niistä:

1. Matkamyyjän ongelma (sekä kaikki muut NP-täydellinen ongelmat ). Tämän tehtävän polynomiratkaisu vastaa luokkien P ja NP yhtäläisyyden vahvistamista .
2. Lukujen hajottaminen alkutekijöiksi .
3. Diskreetti logaritmi äärellisessä kentässä .
4. Piilotettu alaryhmäongelma n generaattorilla .
5. Diskreetti logaritmi elliptisen käyrän pisteiden additiivisessa ryhmässä .

Käytännön arvo

Koska usein on tarpeen laskea funktioiden arvot suurella syötedatalla, polynomialgoritmien löytäminen funktioiden laskemiseen on erittäin tärkeä tehtävä. Uskotaan, että on paljon vaikeampaa laskea funktioita, jotka eivät kuulu luokkaan P, kuin niitä, jotka kuuluvat. Useimmilla luokan P algoritmeilla on monimutkaisuus, joka ei ylitä syöttödatan koon pientä polynomia. Esimerkiksi tavallinen matriisikerto-algoritmi vaatii n 3 kertolaskua (vaikka nopeampiakin algoritmeja on olemassa, kuten Strassenin algoritmi ). Polynomin aste on harvoin suuri. Yksi tällainen tapaus on intialaisten matemaatikoiden vuonna 2002 ehdottama Agrawal-Kayala-Saksena-testi , joka selvittää, onko luku n alkuluku O (log 6 n ) -operaatioissa.

Kirjallisuus

• Thomas H. Kormen ym. Algoritmit: Rakentaminen ja analyysi = Algoritmien johdatus. - 2. painos - M . : "Williams" , 2006. - 1296 s. — ISBN 0-07-013151-1 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Linkit