P = NP problem

Odnos između klasa kompleksnosti P i NP predstavlja nerešen problem teorijskog računarstva. Smatra se da je to najvažniji problem u ovoj naučnoj oblasti - Klejov matematički institut je ponudio nagradu od milion američkih dolara prvoj osobi koja reši ovaj problem.^[2]

U suštini, pitanje P = NP? glasi: ako odgovori na da-ne pitanje koji glase da mogu da se provere brzo (u polinomijalnom vremenu), da li sami odgovori mogu da se izračunaju brzo?

Kao primer može da se uzme problem sume podskupa, problem kod koga je za neko ponuđeno rešenje lako utvrditi da li je ispravno, ali se veruje (nije dokazano) da je pronalaženje rešenja teško. Ako je dat skup celih brojeva, da li neki neprazan podskup ovog skupa ima zbir jednak nuli? Na primer, da li neki podskup skupa {−2, −3, 15, 14, 7, −10} ima zbir jednak nuli? Odgovor da, jer je zbir {−2, −3, −10, 15} jednak nuli može brzo da se proveri pomoću samo nekoliko sabiranja. Međutim, za pronalaženje takvog podskupa bi bilo potrebno mnogo više vremena. Ako je ponuđen odgovor na ovo pitanje, taj odgovor može da se verifikuje u polinomijalnom vremenu, tako da ovaj problem spada u klasu NP.

Odgovor na pitanje P = NP bi odredio da li je probleme kao što je suma podskupa podjednako lako rešiti kao što je lako verifikovati njihova rešenja. Ako bi se ispostavilo da P nije jednako NP, to bi značilo da je neke NP probleme značajno teže rešiti nego verifikovati njihova rešenja.

Ograničenje na probleme odlučivanja (da-ne probleme) nije bitno; rezultujući problem kada se dozvole komplikovaniji odgovori (da li je FP = FNP) je ekvivalentan.^[3]

Istorija[uredi | uredi izvor]

O pitanjima u osnovi ovog problema prvi put se vodila diskusija tokom 1950-ih, u pismima Džona Forbsa Naša mlađeg upućenim Agenciji za nacionalnu sigurnost, i pismima Kurta Gedela poslatih Džonu fon Nojmanu. Preciznu tvrdnju o problemu P nasuprot NP uveo je 1971. godine Stiven Kuk u svom seminalnom radu s naslovom „Kompleksnost procedura dokazivanja teorema”^[4] (a nezavisno se javlja u radu Leonida Levina iz 1973.^[5]) i mnogi ga smatraju najvažniji otvoreni problem u računarskoj nauci.^[6]

Kontekst problema[uredi | uredi izvor]

Relacija između klasa kompleksnosti P i NP se proučava u računarskoj teoriji kompleksnosti, koja se bavi resursima neophodnim tokom izračunavanja kako bi se rešio dati problem. Najčešće posmatrani resursi su vreme (koliko koraka je potrebno da bi se problem rešio) i prostor (koliko memorije je neophodno imati).

U takvoj analizi je neophodno precizirati model računara koji se koristi za izračunavanje. Uobičajeno je da se pretpostavi da je računar deterministički (za dato trenutno stanje računara i za dati bilo koji ulaz, postoji samo jedna moguća akcija koju računar može da preduzme) i sekvencijalan (akcije sprovodi jednu po jednu). Danas (2008. godina), ove pretpostavke su zadovoljene za praktično sve računare koji postoje, čak i za one koji praktikuju paralelno izračunavanje.^[7]^[8]^[9]

U ovoj teoriji, klasa P se sastoji od svih onih problema odlučivanja koji mogu da budu rešeni korišćenjem determinističke sekvencijalne mašine u vremenu koje je polinomijalno u odnosu na veličinu ulaza; klasa NP se sastoji od svih onih problema odlučivanja čija pozitivna rešenja mogu da se verifikuju u polinomijalnom vremenu ako je data prava informacija, ili ekvivalentno, čije rešenje može da se nađe u polinomijalnom vremenu pomoću nedeterminističke mašine.^[10] Jedno od najvećih, ako ne i najveće otvoreno pitanje teorijskog računarstva se tiče odnosa između ove dve klase:

Da li je P jednako NP?

2002. godine je sprovedena anketa među 100 stručnjaka i 61 je rekao da veruje da je odgovor ne, 9 je smatralo da je odgovor da, 22 nije bilo sigurno a 8 je verovalo da je pitanje možda nezavisno u odnosu na trenutno prihvaćene aksiome, pa bi ga stoga bilo nemoguće ni potvrditi niti opovrgnuti.^[7]

Formalne definicije za P i NP[uredi | uredi izvor]

Problem odlučivanja se može posmatrati kao problem koji kao ulaz uzima neku nisku (reč), a kao izlaz daje da ili ne. Ako postoji algoritam (recimo Tjuringova mašina, ili računarski program sa neograničenom memorijom) koji je u stanju da da tačan odgovor za bilo koju ulaznu nisku dužine $n$ u ne više od $c\cdot n^{k}$ koraka, gde su $k$ i $c$ konstante nezavisne od ulazne niske, onda se kaže da je problem rešiv u polinomijalnom vremenu i nalazi se u klasi kompleksnosti P. Formalno, P se definiše kao skup svih jezika koji mogu da budu odlučeni determinističkom polinomijalnom Tjuringovom mašinom. To jest,

P = {L : L=L(M) za neku determinističku polinomijalnu Tjuringovu mašinu M }

gde $L(M)=\{w\in \Sigma ^{*}:M{\text{ prihvata }}w\}$

a deterministička polinomijalna Tjuringova mašina je deterministička Tjuringova mašina M koja zadovoljava sledeća dva uslova:

M se zaustavlja za svaki ulaz w; i
postoji $k\in N$ , takvo da $T_{M}(n)\in \;$ O $(n^{k})$ ,

gde je

T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},\left|w\right|=n\}

i

t_{M}(w)

= broj koraka koji su potrebni da bi se M zaustavila za ulaz w.

NP može na sličan način da se definiše korišćenjem nedeterminističke Tjuringove mašine (tradicionalni način) Međutim, moderan pristup u definisanju NP podrazumeva koncept verifikatora. Formalno, NP se definiše kao skup svih jezika nad konačnom azbukom, za koje postoji verifikator u polinomijalnom vremenu, gde se verifikator definiše na sledeći način.

Neka je $L$ jezik nad konačnom azbukom, $\Sigma$ .

$L\in \mathbf {NP}$ ako i samo ako postoji binarna relacija $R\subset \Sigma ^{*}\times \Sigma ^{*}$ i pozitivan ceo broj $k$ , takav da su sledeća dva uslova zadovoljena:

Za svako $x\in \Sigma ^{*}$ , $x\in L\Leftrightarrow \exists y\in \Sigma ^{*}$ tako da $(x,y)\in R\;$ i $\left|y\right|\in \;$ O $(\left|x\right|^{k})$ ; i
Jezik $L_{R}=\{x\#y:(x,y)\in R\}$ nad $\Sigma \cup \{\#\}$ je odlučiv pomoću Tjuringove mašine.

Tjuringova mašina koja odlučuje $L_{R}$ se naziva verifikatorom za L.

Načelno, verifikator ne mora da radi u polinomijalnom vremenu. Međutim, da bi L bilo unutar NP, neophodno je da postoji verifikator u polinomijalnom vremenu.

NP kompletnost[uredi | uredi izvor]

U rešavanju pitanja da li je P = NP, vrlo je koristan koncept NP-kompletnosti. Neformalno, NP-kompletni problemi su najteži problemi u klasi NP u smislu da ako su neki NP problemi izvan klase P, onda su to NP-kompletni problemi. NP-kompletni problemi su oni NP-teški problemi koji su u klasi NP, a NP-težak problem je onaj problem na koji se bilo koji problem iz klase NP može svesti u polinomijalnom vremenu. Na primer, problem trgovačkog putnika definisan u vidu problema odlučivanja je NP-kompletan, tako da svaki primerak svakog NP problema može mehanički da se transformiše u neki primerak problema trgovačkog putnika i to u polinomijalnom vremenu, tako da je odgovor na početni problem da ako i samo ako je odgovor na dobijeni primerak problema trgovačkog putnika da. Problem trgovačkog putnika je jedan od mnogih NP-kompletnih problema. Ako je bilo koji NP-kompletan problem u klasi P, onda bi sledilo da je P = NP. Međutim, iako je za mnoge važne probleme pokazano da su NP-kompletni, još uvek nije pronađen nijedan brz algoritam za bilo koji od njih.

Na osnovu same definicije, nije očigledno da postoje NP-kompletni problemi. Trivijalan NP-kompletan problem bi mogao da se definiše na sledeći način: ako je dat opis Tjuringove mašine M, za koji se garantuje da će stati u polinomijalnom vremenu, da li postoji ulaz polinomijalne dužine koji će M prihvatiti?^[11] Ovaj problem je u NP, jer za dati ulaz je jednostavno proveriti da li će ga M prihvatiti prostim simuliranjem rada M (pustimo mašinu da izvrši izračunavanje); NP-težak je, jer verifikator za svaku pojedinačnu instancu problema u NP može da se kodira u polinomijalnu mašinu M koja uzima rešenje kao verifikovan ulaz. Onda se pitanje da li je instanca ima rešenje ili ne rešava odgovorom na pitanje da li postoji validan ulaz.

Prvi prirodni problem za koji je pokazano da je NP-kompletan je bio SAT-problem. Ovo je rezultat Kuk-Levinove teoreme; njen dokaz da je SAT problem NP-kompletan sadrži tehničke detalje o Tjuringovim mašinama i kako se one odnose na definiciju NP. Međutim, nakon što je za ovaj problem dokazano da je NP-kompletan, metodom svođenja je postalo mnogo lakše da se za razne druge probleme dokaže da su u ovoj klasi (prostim svođenjem na SAT problem). Tako danas postoji velika klasa naizgled nevezanih problema koji su svi uzajamno svodljivi jedan na drugi, pa u neku ruku predstavljaju isti problem.

Formalna definicija NP-kompletnosti[uredi | uredi izvor]

Postoje mnogi ekvivalentni načini da se opiše NP-kompletnost, ali je u kontekstu pitanja da li je P = NP možda najzgodnije da se NP-kompletni problemi definišu u odnosu na NP probleme.

Neka je L jezik nad konačnom azbukom $\ \Sigma$ .

L je NP-kompletan ako i samo ako su zadovoljena sledeća dva uslova:

$L\in \mathbf {NP}$ ; i
svako $L^{'}\in \mathbf {NP}$ $L^{'}\in \mathbf {NP}$ je u polinomijalnom vremenu svodljivo na L (što se zapisuje kao $L^{'}\leq _{p}L$ $L^{'}\leq _{p}L$ ), gde je $L^{'}\leq _{p}L$ $L^{'}\leq _{p}L$ ako i samo ako su sledeća dva uslova zadovoljena:
1. Postoji $f:\Sigma ^{*}\rightarrow \Sigma ^{*}$ takva da $\forall w\in \Sigma ^{*}(w\in L^{'}\Leftrightarrow f(w)\in L)$ ; i
2. postoji polinomijalna Tjuringova mašina koja se zaustavlja sa $\ f(w)$ na traci za svaki ulaz $\ w$ .

Reference[uredi | uredi izvor]

^ R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
^ „Millennium Prize Problems”. 24. 5. 2000. Arhivirano iz originala 08. 01. 2008. g. Pristupljeno 12. 1. 2008.
^ Scott Aaronson. Complexity Zoo: FP. "FP = FNP if and only if P = NP". http://qwiki.stanford.edu/wiki/Complexity_Zoo#fp}- Arhivirano na sajtu Wayback Machine (26. jul 2010)
^ Cook, Stephen (1971). „The complexity of theorem proving procedures”. Proceedings of the Third Annual ACM Symposium on Theory of Computing. str. 151—158.
^ L. A. Levin (1973). „Universalьnыe zadači perebora” (na jeziku: ruski). 9 (3) (Problems of Information Transmission izd.): 115—116.
^ Fortnow, Lance (2009). „The status of the P versus NP problem” (PDF). Communications of the ACM. 52 (9): 78—86. doi:10.1145/1562164.1562186. Arhivirano iz originala (PDF) 24. 02. 2011. g. Pristupljeno 06. 11. 2019.
^ ^a ^b Gasarch, William I. (2002). „The P=?NP poll.” (PDF). SIGACT News. 33 (2): 34—47. doi:10.1145/1052796.1052804.
^ William I. Gasarch. „The Second P=?NP poll” (PDF). SIGACT News. 74.
^ „Guest Column: The Third P =? NP Poll1” (PDF).
^ Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
^ Scott Aaronson. „PHYS771 Lecture 6: P, NP, and Friends”. Pristupljeno 27. 8. 2007.

Literatura[uredi | uredi izvor]

Cormen, Thomas (2001). Introduction to Algorithms. Cambridge: MIT Press. ISBN 978-0-262-03293-3.
Garey, Michael; Johnson, David (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company. ISBN 978-0-7167-1045-5.
Goldreich, Oded (2010). P, NP, and NP-Completeness. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2. Online drafts
Immerman, N. (1987). „Languages which capture complexity classes”. SIAM Journal on Computing. 16 (4): 760—778. CiteSeerX 10.1.1.75.3035 . doi:10.1137/0216051.
Papadimitriou, Christos (1994). Computational Complexity. Boston: Addison-Wesley. ISBN 978-0-201-53082-7.

Spoljašnje veze[uredi | uredi izvor]

Glavolomka od milion dolara („Politika“, 21. avgust 2010)
Fortnow, L.; Gasarch, W. „Computational complexity”.
Aviad Rubinstein's Hardness of Approximation Between P and NP, winner of the ACM's 2017 Doctoral Dissertation Award.
„P vs. NP and the Computational Complexity Zoo”. 26. 8. 2014 — preko YouTube.

[Ladner-1] R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site.

[CMI_Millennium_Prize_Problems-2] „Millennium Prize Problems”. 24. 5. 2000. Arhivirano iz originala 08. 01. 2008. g. Pristupljeno 12. 1. 2008.

[3] Scott Aaronson. Complexity Zoo: FP. "FP = FNP if and only if P = NP". http://qwiki.stanford.edu/wiki/Complexity_Zoo#fp}- Arhivirano na sajtu Wayback Machine (26. jul 2010)

[4] Cook, Stephen (1971). „The complexity of theorem proving procedures”. Proceedings of the Third Annual ACM Symposium on Theory of Computing. str. 151—158.

[5] L. A. Levin (1973). „Universalьnыe zadači perebora” (na jeziku: ruski). 9 (3) (Problems of Information Transmission izd.): 115—116.

[6] Fortnow, Lance (2009). „The status of the P versus NP problem” (PDF). Communications of the ACM. 52 (9): 78—86. doi:10.1145/1562164.1562186. Arhivirano iz originala (PDF) 24. 02. 2011. g. Pristupljeno 06. 11. 2019.

[poll-7] Gasarch, William I. (2002). „The P=?NP poll.” (PDF). SIGACT News. 33 (2): 34—47. doi:10.1145/1052796.1052804.

[poll2-8] William I. Gasarch. „The Second P=?NP poll” (PDF). SIGACT News. 74.

[poll3-9] „Guest Column: The Third P =? NP Poll1” (PDF).

[10] Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.

[Scott-11] Scott Aaronson. „PHYS771 Lecture 6: P, NP, and Friends”. Pristupljeno 27. 8. 2007.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]