NP-completitudine

În teoria complexității, o problemă de decizie este NP-completă atunci când este atât în NP cât și în NP-hard. Mulțimea problemelor NP-complete este adesea notată cu NP-C sau NPC. Abrevierea NP se referă la „timp nedeterminist polinomial”.

Diagramă Euler pentru mulțimile de probleme P, NP, NP-complete, și NP-dure. Partea stângă este valabilă în ipoteza că P≠NP, în timp ce partea dreaptă este valabilă în ipoteza că P=NP (cu excepția faptului că limbajul vid și complementul acestuia nu sunt NP-complete)

Deși orice soluție la o problemă NP-completă poate fi verificată rapid (în timp polinomial), nu este cunoscut niciun mod eficient de a găsi o soluție dacă nu se cunoaște una; într-adevăr, cea mai notabilă caracteristică a problemelor NP-complete este faptul că nu se cunoaște nicio soluție rapidă pentru ele. Aceasta înseamnă că timpul necesar pentru a rezolva problema folosind orice algoritm cunoscut în prezent crește foarte repede cu dimensiunea problemei. Ca urmare, problema stabilirii dacă este posibil să se rezolve aceste probleme rapid, numită problema P versus NP, este una dintre principalele probleme nerezolvate în informatică astăzi.

Deși înca nu s-a descoperit o metodă de calcul a soluțiilor pentru problemele NP-complete folosind un timp rezonabil, informaticieni și programatori încă se confruntă frecvent cu probleme NP-complete. Problemele NP-complete sunt adesea rezolvate prin utilizarea metodelor euristice și a algoritmilor de aproximare^⁠(d).

Generalități

Problemele NP-complete sunt în NP, mulțimea tuturor problemelor de decizie^⁠(d) ale căror soluții pot fi verificate în timp polinomial; NP poate fi definită echivalent ca mulțimea problemelor de decizie care pot fi rezolvate în timp polinomial pe o mașină Turing nedeterministă. O problemă p din NP este NP-completă dacă orice altă problemă din NP poate fi transformată (sau redusă), la p în timp polinomial.

Problemele NP-complete sunt studiate deoarece capacitatea de a verifica rapid soluții la o problemă (NP) pare a fi corelată cu capacitatea de a rezolva rapid problema (P). Nu se știe dacă fiecare problemă din NP poate fi rezolvată rapid—aceasta se numește problema P versus NP. Dar dacă orice problemă NP-completă poate fi rezolvată rapid, atunci se pot rezolva rapid toate problemele din NP, pentru că definiția unei probleme NP-complete afirmă că fiecare problemă din NP este ușor reductibilă la orice problemă NP-completă („ușor reductibilă” cu sensul că poate fi redusă în timp polinomial). Din acest motiv, se spune adesea că problemele NP-complete sunt mai grele sau mai dificile decât problemele NP, în general.

Definiție formală a NP-completitudinii

O problemă de decizie $\scriptstyle C$ este NP-completă dacă:

1. $\scriptstyle C$ este în NP, și
2. Toate problemele din NP sunt reductibile^⁠(d) la $\scriptstyle C$ în timp polinomial.

$\scriptstyle C$ este în NP demonstrând că o soluție candidat la $\scriptstyle C$ poate fi verificată în timp polinomial.

O problemă care satisface condiția 2 este declarată a fi NP-dură, indiferent dacă îndeplinește sau nu condiția 1.

O consecință a acestei definiții este că, dacă ar exista un algoritm în timp polinomial (pe o mașină Turing universală^⁠(d), sau pe orice altă mașină abstractă Turing-echivalentă^⁠(d)) pentru $\scriptstyle C$ s-ar putea rezolva toate problemele din NP în timp polinomial.

Context

Conceptul de NP-completitudine a fost introdus în 1971 (a se vedea teorema Cook–Levin^⁠(d)), deși termenul NP-complet a fost introdus mai târziu. În conferința Symposium on Theory of Computing^⁠(d) din 1971, a existat o dezbatere aprinsă între informaticieni despre dacă problemele NP-complete pot fi rezolvate în timp polinomial pe o mașină Turing deterministă. John Hopcroft a adus pe toți cei prezenți la conferință la un consens că întrebarea dacă problemele NP-complete sunt rezolvabile în timp polinomial ar trebui amânată pentru o dată ulterioară, deoarece nimeni nu avea nicio demonstrație formală pentru afirmațiile sale, oricare ar fi fost acelea. Atunci s-a născut întrebarea dacă P=NP.

Nimeni nu a fost încă în măsură să determine dacă problemele NP-complete sunt, de fapt, rezolvabile în timp polinomial, ceea ce a făcut ca aceasta să fie una dintre marile probleme nerezolvate din matematică. Clay Mathematics Institute^⁠(d) oferă un 1 milion de dolari recompensă pentru oricine demonstrează că P=NP sau că P≠NP.

Teorema Cook–Levin^⁠(d) afirmă că problema satisfiabilității booleene^⁠(d) este NP-completă (este disponibilă o demonstrație^⁠(d) simplă, dar încă foarte tehnică). În 1972, Richard Karp a demonstrat că sunt mai multe alte probleme NP-complete (a se vedea cele 21 de probleme NP-complete ale lui Karp); astfel, există o clasă de probleme NP-complete (pe lângă problema satisfiabilități booleene). De la rezultatele inițiale, mii de alte probleme s-au dovedit a fi NP-complete prin reducere la alte probleme, anterior demonstrate a fi NP-complete; multe dintre aceste probleme sunt colectate în cartea lui Garey^⁠(d) și Johnson^⁠(d) din 1979 intitulată Computers and Intractability^⁠(d). Pentru mai multe detalii, consultați Introducere în Proiectarea și Analiza Algoritmilor de Anany Levitin.

Probleme NP-complete

Unele probleme NP-complete, cu indicarea reducerilor folosite de obicei pentru a le demonstra NP-completitudinea

Un exemplu interesant este cel problemei izomorfismului grafurilor^⁠(d), problema din teoria grafurilor de a determina dacă există un izomorfism de grafuri între două grafuri. Două grafuri sunt izomorfe dacă unul poate fi transformat în celălalt pur și simplu prin redenumirea nodurilor. Fie aceste două probleme:

• Izomorfismul de grafuri: Este un graf G₁ izomorf cu graful G₂?
• Izomorfismul de subgrafuri: Este un graf G₁ izomorf cu un subgraf al grafului G₂?

Problema izomorfismului de subgrafuri este NP-completă. Problema izomorfismului de grafuri problema este suspectată a nu fi nici în P, nici NP-completă, deși este în NP. Acesta este un exemplu de problemă care este considerată a fi grea, dar nu este considerată a fi NP-completă.

Cel mai simplu mod de a demonstra că o problema nouă este NP-completă este de a demonstra mai întâi că este în NP, și apoi de a o reduce la o problemă NP-completă cunoscută. Prin urmare, este utilă cunoașterea unei mulțimi de probleme NP-complete. Lista de mai jos conține unele probleme NP-complete bine-cunoscute atunci când sunt exprimate ca probleme de decizie.

• Problema satisfiabilității booleene (SAT)^⁠(d)
• Problema rucsacului
• Problema lanțului hamiltonian
• Problema comis-voiajorului (varianta deciziei)
• Problema izomorfismului de subgrafuri^⁠(d)
• Problema sumei submulțimii^⁠(d)
• Problema clicii
• Problema acoperirii nodurilor^⁠(d)
• Problema mulțimii independente^⁠(d)
• Problema mulțimii dominante^⁠(d)
• Problema colorării grafului

La dreapta este o diagramă cu unele dintre probleme și reducerile folosite de obicei pentru a le demonstra NP-completitudinea. În această diagramă, o săgeată de la o problemă la alta indică direcția de reducere. Această diagramă este însă înșelătoare ca descriere a relației matematice dintre aceste probleme, deoarece există o reducere în timp polinomial între oricare două probleme NP-complete; dar se indică aici doar acolo unde demonstrația acestei reduceri în timp polinomial a fost mai simplă.

Există de multe ori doar o mică diferență între o problemă din P și una NP-completă. De exemplu, problema 3-satisfiabilității^⁠(d) problema, o restrângere a problemei satisfiabilității booleene, rămâne NP-completă, pe când problema ușor mai restrânsă a 2-satisfiabilității^⁠(d) este în P (în special, NL-completă^⁠(d)), iar problema mai generală, max. 2-sat. este iarăși NP-completă. Determinarea dacă un graf poate fi colorat în 2 culori este în P, dar în 3 culori este NP-completă, chiar și atunci când este limitată la grafuri planare. Determinarea dacă un graf este ciclic^⁠(d) sau este bipartit este foarte ușoară (în L), dar găsirea unui subgraf bipartit maxim sau a unui subgraf ciclic maxim este NP-completă. O soluție pentru problema rucsacului la orice procent fix din soluția optimă poate fi calculată în timp polinomial, dar găsirea soluției optime este NP-completă.

Rezolvarea problemelor NP-complete 

În prezent, toți algoritmii cunoscuți pentru probleme NP-complete necesită timp superpolinomial în raport cu mărimea intrării, și nu se cunoaște dacă există algoritmi mai rapizi.

Următoarele tehnici se pot aplica pentru a rezolva probleme de calcul în general, iar acestea dau naștere adesea la algoritmi substanțial mai rapizi:

• Aproximarea^⁠(d): în loc să se caute o soluție optimă, se caută o soluție care este cel mult la un factor distanță de optim.
• Randomizare^⁠(d): obținerea unui timp de rulare mediu mai mic, permițând algoritmului să eșueze o oarecare probabilitate redusă. Metoda Monte Carlo^⁠(d) nu este un exemplu bun de algoritm eficient în acest sens anume, deși abordările evoluționiste, cum ar fi algoritmii genetici, ar putea fi.
• Restricționarea: Prin limitarea structurii de intrare (de exemplu, la grafuri planare), sunt de obicei posibili algoritmi mai rapizi.
• Parametrizarea^⁠(d): de multe ori există algoritmi rapizi dacă anumiți parametri de intrare sunt ficși.
• Euristică: Un algoritm care funcționează „destul de bine”, în multe cazuri, dar pentru care nu există nici o dovadă că ea este întotdeauna și rapid și mai și produce un rezultat bun. Abordările metaeuristice^⁠(d) sunt adesea folosite.

Un exemplu de algoritm euristic este un algoritm greedy de colorare^⁠(d) suboptim $\scriptstyle O(n\log n)$ folosit pentru colorarea grafurilor în faza de alocare de regiștri^⁠(d) de la unele compilatoare, o tehnică numită alocare globală de regiștri cu colorare de graf. Fiecare nod este o variabilă, muchiile înseamnă utilizarea variabilelor în același timp, și culorile indică registrul alocat pentru fiecare variabilă. Deoarece majoritatea mașinilor RISC au un număr destul de mare de regiștri de uz general, chiar și o abordare euristică este destul de eficientă pentru această aplicație.

Completitudinea în raport cu diferite tipuri de reducere

În definiția NP-completitudinii dată mai sus, termenul de reducere a fost utilizat în sensul de reducere many-one^⁠(d) în timp polinomial.

Un alt tip de reducere este reducerea Turing în timp polinomial. O problemă $\scriptstyle X$ este Turing-reductibilă în timp polinomial la o problemă $\scriptstyle Y$ dacă, având o subrutină care rezolvă $\scriptstyle Y$ în timp polinomial, s-ar putea scrie un program care apelează această subrutină și rezolvă $\scriptstyle X$ în timp polinomial. Acest lucru se deosebește de reductibilitatea many-one, care are restricția că programul poate doar apela subrutina o singură dată, iar valoarea returnată de subprogram trebuie să fie valoarea de returnare a programului.

Dacă se definește conceptul analog NP-completitudinii cu reduceri Turing în loc de mai reduceri many-one, mulțimea de probleme rezultată nu va fi mai mică decât cea a problemelor NP-complete; este o întrebare deschisă însă dacă este mai mare.

Un alt tip de reducere adesea folosit pentru a defini NP-completitudinea este reducerea many-one în spațiu logaritmic^⁠(d), o reducere many-one care poate fi calculată cu o complexitate logaritmică în spațiu. Deoarece fiecare calcul care poate fi făcut în spațiu logaritmic poate fi, de asemenea, efectuat în timp polinomial, rezultă că dacă există o reducere many-one în spațiu logaritmic, atunci există și o reducere many-one în timp polinomial. Acest tip de reducere este mai rafinată decât mai cunoscuta reducere many-one în timp polinomial și permite distingerea mai multor clase, cum ar fi cea a problemelor P-completitudine^⁠(d). Întrebarea dacă în aceste tipuri de reduceri definiția NP-completitudinii se modifică este încă o problemă deschisă. Toate problemele NP-complete cunoscute în prezent sunt problemele NP-complete sub reduceri în spațiu logaritmic. Într-adevăr, problemele NP-complete cunoscute în prezent rămân probleme NP-complete chiar și cu reduceri mult mai slabe. Se știe însă că reducerile AC^0⁠(d) definesc o clasă strict mai mică decât reducerile în timp polinomial.

Denumirea

Conform lui Donald Knuth, numele de „NP-complet” a fost popularizat de către Alfred Aho^⁠(d), John Hopcroft și Jeffrey David Ullman^⁠(d) în celebrul lor manual „The Design and Analysis of Computer Algorithms”. El declara că aceștia au introdus modificarea într-o variantă de corectură^⁠(d) a cărții (de la „polinomial-complet”), în conformitate cu rezultatele unui sondaj de opinie a realizat în comunitatea informaticienilor teoreticieni^⁠(d). Alte sugestii făcute în sondaj includeau „herculean”, „formidabil”, „fiert tare” — propus de Steiglitz în onoarea lui Cook, și acronimul „PET” avansat de Shen Lin — cu semnificația „probabil exponențial în timp”; dar, în funcție de direcția în care ar fi mers problema P versus NP, ar putea însemna „demonstrabil (provably) exponențial în timp” sau „anterior (previously) exponențială în timp”.

Greșeli frecvente de înțelegere

Sunt frecvente următoarele greșeli de înțelegere a conceptului.

• „Problemele NP-complete sunt problemele cele mai dificile cunoscute.” Deoarece problemele NP-complete sunt în NP, timpul lor de funcționare este de cel mult exponențial. Cu toate acestea, sunt unele probleme care se poate demonstra că necesită mai mult timp, de exemplu aritmetica Presburger^⁠(d).
• „Problemele NP-complete sunt dificile, deoarece există atât de multe soluții diferite.” Pe de o parte, există multe probleme care au un spațiu de soluții la fel de mare, dar care poate fi rezolvate în timp polinomial (de exemplu, arborele minim de acoperire). Pe de altă parte, există probleme NP-probleme cu cel mult o soluție care sunt NP-dure în raport cu reducerea randomizată în timp polinomial (vezi teorema Valiant–Vazirani^⁠(d)).
• „Rezolvarea problemelor NP-complete necesită timp exponențial.” În primul rând, acest lucru ar însemna că P ≠ NP, afirmație încă nedemonstrată. Mai mult, unele probleme NP-complete au de fapt algoritmi de funcționare superpolinomiali, dar subexponențiali, de exemplu de complexitate O(2^√nn). De exemplu, mulțimile independente^⁠(d) și mulțimile dominante^⁠(d) sunt NP-complete atunci când sunt limitate la grafuri planare, dar pot fi rezolvate în timp subexponențial pe grafuri planare folosind teorema separatorului planar^⁠(d).
• „Toate cazurile de probleme NP-complete sunt dificile.”  Adesea, unele cazuri, sau chiar majoritatea cazurilor, pot fi ușor de rezolvat în timp polinomial. Cu toate acestea, în cazul în care P ≠ NP, orice algoritm în timp polinomial trebuie să greșească într-un număr de cazuri mai mult decât polinomial de intrări de o anumită dimensiune.
• "Dacă P=NP, toate cifrurile criptografice pot fi sparte." Chiar și o problemă în timp polinomial poate fi foarte dificil de rezolvat, în practică, dacă polinomul are grad sau constante sunt suficient de mari. De exemplu, cifrurile cu cheie de lungime fixă, cum ar fi Advanced Encryption Standard, toate pot fi sparte în timp constant (și sunt, prin urmare, deja în P), dar cu tehnologia actuală constanta aceea poate depăși vârsta universului.

Proprietăți

Vizualizarea problemei deciziei ca pe un limbaj formal în unele codificări fixe, mulțimea NPC a tuturor problemelor NP-complete nu este închisă în raport cu:

• reuniunea
• intersecția
• concatenarea
• Kleene star

Nu se știe dacă NPC este închisă în raport cu complementarea, deoarece NPC=co-NPC^⁠(d) dacă și numai dacă NP=co-NP^⁠(d), iar această din urmă relație este o întrebare deschisă^⁠(d).

Referințe

Surse

• Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability^⁠(d) (în engleză). New York: W.H. Freeman. ISBN 0-7167-1045-5.  This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
• Cook, S.A. (1971). „The complexity of theorem proving procedures”. Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York (în engleză). pp. 151–158. doi:10.1145/800157.805047. 
• Dunne, P.E. „An annotated list of selected NP-complete problems” (în engleză). COMP202, Dept. of Computer Science, University of Liverpool^⁠(d). Accesat în 21 iunie 2008. 
• Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.^⁠(d); Woeginger, G^⁠(d). „A compendium of NP optimization problems” (în engleză). KTH NADA, Stockholm. Accesat în 21 iunie 2008. Mentenanță CS1: Nume multiple: lista autorilor (link)
• Dahlke, K. „NP-complete problems”. Math Reference Project (în engleză). Accesat în 21 iunie 2008. 
• Karlsson, R. „Lecture 8: NP-complete problems” (PDF). Dept. of Computer Science, Lund University, Sweden. Arhivat din original (PDF) la 19 aprilie 2009. Accesat în 21 iunie 2008. 
• Sun, H.M. „The theory of NP-completeness” (în engleză). Information Security Laboratory, Dept. of Computer Science, National Tsing Hua University^⁠(d), Hsinchu City, Taiwan. Arhivat din original (PPT) la 2 septembrie 2009. Accesat în 21 iunie 2008. 
• Jiang, J.R. „The theory of NP-completeness” (PPT) (în engleză). Dept. of Computer Science and Information Engineering, National Central University^⁠(d), Jhongli City, Taiwan. Accesat în 21 iunie 2008. 
• Cormen, T.H.; Leiserson, C.E.^⁠(d); Rivest, R.L.; Stein, C.^⁠(d) (2001). „Chapter 34: NP–Completeness”. Introduction to Algorithms^⁠(d) (în engleză) (ed. 2nd). MIT Press and McGraw-Hill. pp. 966–1021. ISBN 0-262-03293-7. 
• Sipser, M. (1997). „Sections 7.4–7.5 (NP-completeness, Additional NP-complete Problems)”. Introduction to the Theory of Computation. PWS Publishing. pp. 248–271. ISBN 0-534-94728-X. 
• Papadimitriou, C. (1994). „Chapter 9 (NP-complete problems)”. Computational Complexity (în engleză) (ed. 1st). Addison Wesley. pp. 181–218. ISBN 0-201-53082-1. 
• Computational Complexity of Games and Puzzles
• Tetris is Hard, Even to Approximate
• Minesweeper is NP-complete! Arhivat în 16 decembrie 2006, la Wayback Machine.
• Bern, Marshall (1990). „Faster exact algorithms for Steiner trees in planar networks”. Networks (în engleză). 20 (1): 109–120. doi:10.1002/net.3230200110. .
• Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006). „Exact algorithms for the Hamiltonian cycle problem in planar graphs”. Operations Research Letters (în engleză). 34 (3): 269–274. doi:10.1016/j.orl.2005.04.013. .
• Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L. author3-link = Hans L. Bodlaender; Fomin, Fedor V. (2005). „Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions”. Proc. 13th European Symposium on Algorithms (ESA '05). Lecture Notes in Computer Science (în engleză). 3669. Springer-Verlag. pp. 95–106. doi:10.1007/11561071_11. ISBN 978-3-540-29118-3. .
• Lipton, Richard J.; Tarjan, Robert E. (1980). „Applications of a planar separator theorem”. SIAM Journal on Computing^⁠(d) (în engleză). 9 (3): 615–627. doi:10.1137/0209046. .

Lectură suplimentară

• Scott Aaronson^⁠(d), NP-complete Problems and Physical Reality, ACM SIGACT^⁠(d) News, Vol. 36, No. 1. (March 2005), pp. 30–52.
• Lance Fortnow^⁠(d), The status of the P versus NP problem, Communications of the ACM^⁠(d), Vol. 52, No. 9. (2009), pp. 78–86.