P (složenost)

U računarskoj teoriji složenosti, P poznata kao PTIME ili DTIME (n^O(1)) je jedna od fundamentalnih klasa složenosti. Ona sadrži sve probleme odlučivanja koji mogu da se reše pomoću determinističke Tjuringove mašine korišćenjem polinomne količine vremena računarske obrade t.j. polinomijalnog vremena. Kobhamova teza utvrđuje da je P klasa računarskih problema koji mogu „efikasno da se reše“ t.j. „traktabilni su“. U praksi neki problemi koji nisu u klasi P imaju praktično rešenje, a neki koji su u P nemaju.

Definicija

Jezik L je u P ako i samo ako postoji deterministička Tjuringova mašina M takva da:

• M radi u polinomijalnom vremenu za sve ulaze
• za sve x iz L, M daje 1
• za sve x koji nisu iz L, M daje 0

Na P može da se gleda kao na unifromnu familiju logičkih kola. Jezik L je u P ako i samo ako postoji uniformna familija logičkih kola u polinomijalnom vremenu $\{C_{n}:n\in \mathbb {N} \}$, takva da:

• za svako $n\in \mathbb {N}$, $C_{n}$ uzima n bitova na ulazu i na izlazu daje 1 bit
• za svako x iz L, $C_{|x|}(x)=1$
• za svako x koje nije u L, $C_{|x|}(x)=0$

Definicija kola može da bude slabija tako što će se koristiti samo logspace uniformna familija kola, bez promene klase složenosti.

Značajni problemi u P

Za P se zna da sadrži mnoge prirodne probleme uključujući verzije odlučivanja linearnog programiranja, izračunavanja najvećeg zajedničkog delioca i nalaženje maksimalnog uklapanja. 2002. godine je pokazano da je problem određivanja da li je neki broj prost broj, takođe u P. Srodna klasa funkcijskih problema je FP. Nekoliko funkcijskih problema su komletni za P, uključujući st povezanost (dostupnost) na alternirajućim grafovima. U članku o P kompletnim problemima dalje se navode relevantni problemi iz P.

Relacije prema drugim klasama

Generalizacija P je NP koja je klasa problema odlučivanja koji izvršava nedeterministička Tjuringova mašina u polinomijalnom vremenu. Isto tako, to je klasa problema odlučivanja gde svaka pojava „da“ nosi potvrdu polinomijalne veličine, a potvrde mogu da se provere pomoću determinističke Tjuringove mašine u polinomijalnom vremenu. Klasa problema za koje je ovo istina za pojave „ne“, naziva se co-NP. P je, jednostavno, podskup NP i co-NP. Većina stručnjaka veruje da se radi o pravom podskupu, iako to još uvek nije dokazano (${P}\subseteq {\mbox{NP}}$P ≠ NP hipoteza). Još jedan nerešeni problem je da li je NP = co-NP (negativni odgovor implicira ${P}\subseteq {\mbox{NP}}$). Zna se da je P najmanje veličine L – klase problema odlučivih u okviru logaritamske količine memorijskog prostora. Odlučivanje koje koristi $O(\log n)$ prostora, ne može da traje duže od $2^{O(\log n)}=n^{O(1)}$ zato što je to ukupan broj mogućih konfiguracija i tako sledi je L podskup P. Drugi važan problem je da li je L = P. Znamo da je P = AL, skupu problema rešivih u logaritamskoj memoriji pomoću alternirajuće Tjuringove mašine. Za P se zna da nije veći od PSPACE – klase problema odlučivih u polinomijalnom prostoru. Opet, da li je P = PSPACE je otvoren problem. Da zaključimo:

${\mbox{L}}\subseteq {\mbox{AL}}={\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}.$

Ovde je EXPTIME klasa problema rešivih u eksponencijalnom vremenu. Od svih klasa koje su prikazane, zna se za samo dve striktne pripadnosti:

• P se striktno sadrži u EXPTIME. Shodno tome, svi EXPTIME – teški problemi, leže van P i barem jedna od pripadnosti desno od P je stroga (u stvari, široko rasprostranjeno verovanje je da su sve tri stroge).
• L je striktno sadržana u PSPACE.

Najteži problemi u P su P – kompletni problemi.

Još jedna generalizacija P je P/poly ili neuniformno polinomijalno vreme. Ako je problem u P/poly, onda može da bude rešen u determinističkom polinomijalnom vremenu uz uslov da je dat pomoćni niz (advice string) koji zavisi jedino od dužine ulaza. Za razliku od NP, mašina sa polinomijalnim vremenom nema potrebe za detekcijom pogrešnih pomoćnih nizova – ona nije verifikator. P/poly je velika klasa koja sadrži skoro sve praktične probleme, uključujući sve iz BPP. Ako sadrži NP, tada se polinomijalna hijerarhija skraćuje na drugi nivo. Sa druge strane, ova klasa sadrži i neke probleme na koje ne nailazimu u praksi uključujući neodlučive probleme kao što je unarna vizija bilo kog neodlučivog problema. Jin-Ji Kai i D. Sivakumar, su 1999. godine, razrađujući teze iz rada Micunori Ogihare, pokazali da ako postoji oskudan jezik (sparse language) koji je P-kompletan, onda važi L = P.

Osobine

Algoritmi sa polinomijalnim vremenom su zatvoreni prilikom sastavljanja. Ovo znači da ako neko napiše funkciju koja je vremenski polinomijalna, pod pretpostavkom da se pozivi funkcija odvijaju u konstantnom vremenu, a pozvane funkcije se, takođe, izvršavaju u polinomijalnom vremenu, tada ceo algoritam radi u polinomijalnom vremenu. Jedna posledica ovoga je da je P niska po sebi. To je, takođe, jedan od osnovnih razloga da se P posmatra kao klasa nezavisna od mašine. Svaka odlika mašine, kao na primer nasumičan (slučajan) pristup (random access) koja se može simulirati u polinomijalnom vremenu, može se predstaviti glavnim algoritmom u polinomijalnom vremenu i tako svesti na algoritam koji se izvodi na jednostavnijoj mašinu, isto tako u polinomijalnom vremenu.

Jezici u P su takođe zatvoreni kod negacija, preseka, unija, konkatenacija, Klinijevog zatvaranja, inverzije, homomorfizma i komplementacije.

Dokazi o postojanju algoritama polinomijalnog vremena

Zna se da neki problemi mogu da se reše u polinomijalnom vremenu, iako ne postoje konkretni algoritmi za njihovo rešavanje. Teorema Robertsona i Sejmura garantuje da postoji konačna lista zabranjenih podgrafova koji opredeljuju, na primer, skup grafova koji mogu biti postavljeni na torus. Štaviše, Robertson i Sejmur su pokazali da postoji O(n³) algoritam za određivanje da li neki graf sadrži drugi graf kao podgraf. To dovodi do nekonstruktivnog dokaza da, teoretski, postoji algoritam u polinomijalnom vremenu za određivanje da li zadati graf može da se postavi na torus, bez obzira na činjenicu da takav, konkretan, algoritam ne postoji.

Alternativne karakterizacije

U deskriptivnoj složenosti (descriptive complexity), klasa P može da se opiše problemima izraženim u FO(LFP), logikom prvog reda sa operatorom najmanje fiksne tačke (least fixed point) dodatim na uređenu strukturu. U knjizi Imermana iz 1999. godine o deskriptivnoj složenosti, i sebi. 2001. godine je objavljeno da PTIME odgovara pozitivnim gramatikama konkatenacije slogova (range concatenation grammars).

Istorija

Kozen tvrdi da su Kobem i Edmonds „generalno zaslužni za izum pojma polinomijalnog vremena“. Kobem je izmislio klasu, kao moćan način za karakterizaciju efikasnih algoritama, što je dovela do Kobemove teze. Ipak, H. C. Poklington je još davne 1910. godine objavio rad u kome je analizirao dva algoritma za rešavanje kvadratne kongruencije. On je uvideo da je jedan utrošio vreme „proporcionalno stepenu logaritma modula“, a drugi vreme „proporcionalno samom modulu ili njegovom kvadratnom korenu“. Tako je Poklington napravio jasnu razliku između algoritma koji se izvršava u polinomijalnom vremenu u odnosu na drugi, koji se ne izvršava u polinomijalnom vremenu.

Literatura

• Kozen, Dexter C. (2006). Theory of Computation. Springer. str. 4. ISBN 978-1-84628-297-3. 
• Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. ISBN 978-3-642-14846-0. 
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to automata theory, languages, and computation (2. izd.). Boston: Addison-Wesley. str. 425–426. ISBN 978-0-201-44124-6. 
• Kobham Alan (1965). "The intrinsic computational difficulty of functions".
• Tomas H. Kormen, Čarls E. Lajserson, Ronald Lin Rivest i Kliford Stajn, Introduction to Algorithms (Uvod u algoritme), drugo izdanje. MIT Press i McGraw–Hill, 2001. Section 34.1: Polynomial time. str. 971-979.
• Christos H. Papadimitriou (1994). Computational complexity.
• Sipser, Michael (2006). Introduction to the Theory of Computation (2nd izd.). 

.