Vizualizare sursă pentru „NP-completitudine”

[[Fișier:P_np_np-complete_np-hard.svg|dreapta|miniatura|300x300px|[[Diagramă Euler]] pentru mulțimile de probleme [[P (teoria complexității)|P]], [[NP (teoria complexității)|NP]], NP-complete, și [[NP-hard|NP-dure]]. Partea stângă este valabilă în ipoteza că [[Clasele de complexitate P și NP|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)]]
În [[teoria complexității]], o problemă de decizie este '''NP-completă''' atunci când este atât în [[NP (teoria complexității)|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 „[[Mașină Turing nedeterministă|timp nedeterminist]] [[Complexitate în timp|polinomial]]”.

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ă [[Clasele de complexitate P și NP|problema P versus NP]], este una dintre principalele [[Lista problemelor nerezolvate din informatică|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, [[Informatician|informaticieni]] și [[Programator|programatori]] încă se confruntă frecvent cu probleme NP-complete. Problemele NP-complete sunt adesea rezolvate prin utilizarea metodelor [[Euristică|euristice]] și a {{Ill-wd|Q621751|3=algoritmilor de aproximare}}.

== Generalități ==
Problemele NP-complete sunt în [[NP (teoria complexității)|NP]], mulțimea tuturor {{Ill-wd|Q3262192|3=problemelor de decizie}} 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 (teoria complexității)|P]]). Nu se știe dacă fiecare problemă din NP poate fi rezolvată rapid—aceasta se numește [[Clasele de complexitate P și NP|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 <math>\scriptstyle C</math> este NP-completă dacă:
# <math>\scriptstyle C</math> este în NP, și
# Toate problemele din NP sunt {{Ill-wd|Q3300648|3=reductibile}} la <math>\scriptstyle C</math> în timp polinomial.<ref>{{cite book|author=J. van Leeuwen|year=1998|title=Handbook of Theoretical Computer Science|publisher=Elsevier|ISBN=0-262-72014-0|page=84}}</ref>
<math>\scriptstyle C</math> este în NP demonstrând că o soluție candidat la <math>\scriptstyle C</math> poate fi verificată în timp polinomial.

O problemă care satisface condiția 2 este declarată a fi [[NP-hard|NP-dură]], indiferent dacă îndeplinește sau nu condiția 1.<ref>{{cite book|author=J. van Leeuwen|year=1998|title=Handbook of Theoretical Computer Science|publisher=Elsevier|ISBN=0-262-72014-0|page=80}}</ref>

O consecință a acestei definiții este că, dacă ar exista un algoritm în timp polinomial (pe o {{Ill-wd|Q2703890|3=mașină Turing universală}}, sau pe orice altă {{Ill-wd|Q197970|3=mașină abstractă Turing-echivalentă}}) pentru <math>\scriptstyle C</math> s-ar putea rezolva toate problemele din NP în timp polinomial.

== Context ==
Conceptul de NP-completitudine a fost introdus în 1971 (a se vedea {{Ill-wd|Q377276|3=teorema Cook–Levin}}), deși termenul ''NP-complet'' a fost introdus mai târziu. În conferința {{Ill-wd|Q7661893}} 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|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 ale matematicii|probleme nerezolvate din matematică]]. {{Ill-wd|Q857975}} oferă un 1 milion de dolari recompensă pentru oricine demonstrează că P=NP sau că P≠NP.

{{Ill-wd|Q377276|3=Teorema Cook–Levin}} afirmă că {{Ill-wd|Q875276|3=problema satisfiabilității booleene}} este NP-completă (este disponibilă {{Ill-wd|Q377276|3=o demonstrație}} 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|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 {{Ill-wd|Q6830528|3=Garey}} și {{Ill-wd|Q92801|3=Johnson}} din 1979 intitulată ''{{Ill-wd|Q938821}}''.<ref name="GareyJohnson">{{cite book|last1=Garey|first1=Michael&nbsp;R.|authorlink1=Michael R. Garey|last2=Johnson|first2=D.&nbsp;S.|authorlink2=David S. Johnson|title={{Ill-wd|Q938821}}|year=1979|ISBN=0-7167-1045-5|pages=x+338|url=|doi=|series=A Series of Books in the Mathematical Sciences|editor={{Ill-wd|Q470505}}|publisher=W.&nbsp;H.&nbsp;Freeman and Co.|location=San Francisco, Calif.|mr=519066|ref=harv}}</ref>
Pentru mai multe detalii, consultați ''Introducere în Proiectarea și Analiza Algoritmilor'' de Anany Levitin.

== Probleme NP-complete ==
[[Fișier:Relative_NPC_chart.svg|dreapta|miniatura|Unele probleme NP-complete, cu indicarea reducerilor folosite de obicei pentru a le demonstra NP-completitudinea]]
Un exemplu interesant este cel {{Ill-wd|Q3738036|3=problemei izomorfismului grafurilor}}, problema din [[teoria grafurilor]] de a determina dacă există un {{Ill-wd|Q303100|3=izomorfism de grafuri}} între două grafuri. Două grafuri sunt [[Izomorfism|izomorfe]] dacă unul poate fi [[Izomorfism|transformat]] în celălalt pur și simplu prin redenumirea nodurilor. Fie aceste două probleme:
* Izomorfismul de grafuri: Este un graf G<sub>1</sub> izomorf cu graful G<sub>2</sub>?
* Izomorfismul de subgrafuri: Este un graf G<sub>1</sub> izomorf cu un subgraf al grafului G<sub>2</sub>?
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.
{{colbegin|25em}}
* {{Ill-wd|Q875276|3=Problema satisfiabilității booleene (SAT)}}
* [[Problema rucsacului]]
* [[Problema drumului hamiltonian|Problema lanțului hamiltonian]]
* [[Problema comis-voiajorului]] (varianta deciziei)
* {{Ill-wd|Q2528185|3=Problema izomorfismului de subgrafuri}}
* {{Ill-wd|Q1154420|3=Problema sumei submulțimii}}
* [[Problema clicii]]
* {{Ill-wd|Q924362|3=Problema acoperirii nodurilor}}
* {{Ill-wd|Q1060343|3=Problema mulțimii independente}}
* {{Ill-wd|Q2915204|3=Problema mulțimii dominante}}
* [[Colorarea grafurilor|Problema colorării grafului]]
{{colend}}
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 {{Ill-wd|Q875276|3=3-satisfiabilității}} problema, o restrângere a problemei satisfiabilității  booleene, rămâne NP-completă, pe când problema ușor mai restrânsă a {{Ill-wd|Q4596967|3=2-satisfiabilității}} este în P (în special, {{Ill-wd|Q6954626|3=NL-completă}}), 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 [[Graf planar|grafuri planare]]. Determinarea dacă un graf este {{Ill-wd|Q622506|3=ciclic}} sau este [[Graf bipartit|bipartit]] este foarte ușoară (în [[L (clasă de complexitate)|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 [[Complexitate în 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:
* {{Ill-wd|Q621751|3=Aproximarea}}: în loc să se caute o soluție optimă, se caută o soluție care este cel mult la un factor distanță de optim.
* {{Ill-wd|Q583461|3=Randomizare}}: obținerea unui [[Complexitate în timp|timp de rulare]] mediu mai mic, permițând algoritmului să eșueze o oarecare probabilitate redusă. {{Ill-wd|Q232207|3=Metoda Monte Carlo}} nu este un exemplu bun de algoritm eficient în acest sens anume, deși abordările evoluționiste, cum ar fi [[Algoritm genetic|algoritmii genetici]], ar putea fi.
* Restricționarea: Prin limitarea structurii de intrare (de exemplu, la grafuri planare), sunt de obicei posibili algoritmi mai rapizi.
* {{Ill-wd|Q1570441|3=Parametrizarea}}: 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 {{Ill-wd|Q1385229|3=metaeuristice}} sunt adesea folosite.
Un exemplu de algoritm euristic este un {{Ill-wd|Q5601715|3=algoritm greedy de colorare}} suboptim <math>\scriptstyle O(n\log n)</math> folosit pentru [[Colorarea grafurilor|colorarea grafurilor]] în faza de {{Ill-wd|Q1343660|3=alocare de regiștri}} de la unele compilatoare, o tehnică numită [[Graph-coloring global register allocation|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 {{Ill-wd|Q3300648|3=reducere many-one}} în timp polinomial.

Un alt tip de reducere este reducerea Turing în timp polinomial. O problemă <math>\scriptstyle X</math> este Turing-reductibilă în timp polinomial la o problemă <math>\scriptstyle Y</math> dacă, având o subrutină care rezolvă <math>\scriptstyle Y</math> în timp polinomial, s-ar putea scrie un program care apelează această subrutină și rezolvă <math>\scriptstyle X</math> î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 {{Ill-wd|Q448582|3=reducerea many-one în spațiu logaritmic}}, o reducere many-one care poate fi calculată cu o complexitate logaritmică în spațiu. Deoarece fiecare calcul care poate fi făcut în [[L (clasă de complexitate)|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 {{Ill-wd|Q905789}}. Î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.<ref>{{Citat revistă|nume=Agrawal|nume2=Allender|nume3=Rudich|prenume=M.|prenume2=E.|prenume3=Steven|legătură-autor=Manindra Agrawal|legătură-autor3=Steven Rudich|an=1998|titlu=Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem|journal=Journal of Computer and System Sciences|volum=57|număr=2|pagini=127–143|publisher={{Ill-wd|Q2076913}}|issn=1090-2724|ISSN=1090-2724|doi=10.1006/jcss.1998.1583|DOI=10.1006/jcss.1998.1583|ref=harv|postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->}}</ref> Se știe însă că reducerile {{Ill-wd|Q287954|3=AC<sup>0</sup>}} definesc o clasă strict mai mică decât reducerile în timp polinomial.<ref>{{Citat revistă|nume=Agrawal|nume2=Allender|nume3=Impagliazzo|nume4=Pitassi|nume5=Rudich|prenume=M.|prenume2=E.|prenume3=R.|prenume4=T.|prenume5=Steven|legătură-autor=Manindra Agrawal|legătură-autor4=Toniann Pitassi|legătură-autor5=Steven Rudich|an=2001|titlu=Reducing the complexity of reductions|journal=Computational Complexity|volum=10|număr=2|pagini=117–138|publisher=Birkhäuser Basel|issn=1016-3328|ISSN=1016-3328|doi=10.1007/s00037-001-8191-1|DOI=10.1007/s00037-001-8191-1|ref=harv|postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->}}</ref>

== Denumirea ==
Conform lui [[Donald E. Knuth|Donald Knuth]], numele de „NP-complet” a fost popularizat de către {{Ill-wd|Q62898}}, [[John Hopcroft]] și {{Ill-wd|Q92794}} în celebrul lor manual „The Design and Analysis of Computer Algorithms”. El declara că aceștia au introdus modificarea într-o {{Ill-wd|Q452861|3=variantă de corectură}} a cărții (de la „polinomial-complet”), în conformitate cu rezultatele unui sondaj de opinie a realizat în comunitatea {{Ill-wd|Q2878974|3=informaticienilor teoreticieni}}.<ref>[[Donald E. Knuth|Don Knuth]], Tracy Larrabee, and Paul M. Roberts, ''[http://tex.loria.fr/typographie/mathwriting.pdf Mathematical Writing]'' § 25, ''MAA Notes No. 14'', MAA, 1989 (also [[Universitatea Stanford|Stanford]] Technical Report, 1987).</ref> Alte sugestii făcute în sondaj<ref>{{Citat revistă|nume=Knuth|prenume=D. F.|an=1974|titlu=A terminological proposal|url=http://portal.acm.org/citation.cfm?id=1811130|journal=SIGACT News|volum=6|număr=1|pagini=12–18|doi=10.1145/1811129.1811130|DOI=10.1145/1811129.1811130|access-date=2010-08-28|accessdate=2010-08-28|ref=harv}}</ref> includeau „herculean”, „formidabil”, „fiert tare”{{mdash}} propus de Steiglitz în onoarea lui Cook, și acronimul „PET” avansat de Shen Lin{{mdash}} cu semnificația „probabil exponențial în timp”; dar, în funcție de direcția în care ar fi mers [[Clasele de complexitate P și NP|problema P versus NP]], ar putea însemna „demonstrabil (''provably'') exponențial în timp” sau „anterior (''previously'') exponențială în timp”.<ref>See the poll, or [http://www.cs.princeton.edu/~wayne/kleinberg-tardos/08np-complete-2x2.pdf] {{Webarchive|url=https://web.archive.org/web/20110607082034/http://www.cs.princeton.edu/~wayne/kleinberg-tardos/08np-complete-2x2.pdf |date=2011-06-07 }}.</ref>

== Greșeli frecvente de înțelegere ==
Sunt frecvente următoarele greșeli de înțelegere a conceptului.<ref>{{Citat știre|title=DNA computer helps travelling salesman|url=http://www.nature.com/news/2000/000113/full/news000113-10.html|prenume=Philip|nume=Ball|doi=10.1038/news000113-10}}</ref>
* ''„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 {{Ill-wd|Q956059|3=aritmetica Presburger}}.
* ''„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, [[Arbore minim de acoperire|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 {{Ill-wd|Q7911648|3=teorema Valiant–Vazirani}}).
* ''„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<sup>{{sqrt|''n''}}</sup>''n''). De exemplu, {{Ill-wd|Q1060343|3=mulțimile independente}} și {{Ill-wd|Q2915204|3=mulțimile dominante}} sunt NP-complete atunci când sunt limitate la [[Graf planar|grafuri planare]], dar pot fi rezolvate în timp subexponențial pe [[Graf planar|grafuri planare]] folosind {{Ill-wd|Q7200963|3=teorema separatorului planar}}.<ref>{{harvtxt|Bern|1990}}; {{harvtxt|Deĭneko|Klinz|Woeginger|2006}}; {{harvtxt|Dorn|Penninks|Bodlaender|Fomin|2005}}; {{harvtxt|Lipton|Tarjan|1980}}.</ref>
* ''„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.<ref>{{Citat revistă|nume=Hemaspaandra|nume2=Williams|prenume=L. A.|prenume2=R.|an=2012|titlu=SIGACT News Complexity Theory Column 76|journal=ACM SIGACT News|volum=43|număr=4|pagină=70|doi=10.1145/2421119.2421135|DOI=10.1145/2421119.2421135}}</ref>
* ''"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 [[AES|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
* [[Închidere Kleene|Kleene star]]
Nu se știe dacă NPC este închisă în raport cu complementarea, deoarece NPC={{Ill-wd|Q1142354|3=co-NPC}} [[dacă și numai dacă]] NP={{Ill-wd|Q955748}}, iar această din urmă relație este o {{Ill-wd|Q1321906|3=întrebare deschisă}}.<ref>{{Citation|title=Complexity and Cryptography: An Introduction|year=2006|last1=Talbot|last2=Welsh|first1=John|first2=D. J. A.|author2-link=Dominic Welsh|url=https://books.google.com/books?id=y_ZwupY8pzUC&pg=PA57|page=57|publisher=Cambridge University Press|isbn=9780521617710|ISBN=9780521617710|quote=The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.}}</ref>

== Referințe ==

=== Citări ===
<references />

=== Surse ===

{{refbegin |colwidth = 30em}}
* {{Cite book
 |last1 = Garey
 |first1 = M.R.
 |author1-link = Michael Garey
 |author2 = Johnson, D.S.
 |author2-link = David S. Johnson 
 |title = {{Ill-wd|Q938821}}
 |year = 1979
 |publisher = W.H. Freeman
 |location = New York
 |ISBN = 0-7167-1045-5
 |language = engleză
}}  This book is a classic, developing the theory, then cataloguing ''many'' NP-Complete problems.
* {{Cite conference
 |last = Cook
 |first = S.A.
 |authorlink = Stephen A. Cook
 |title = The complexity of theorem proving procedures
 |booktitle = Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York
 |year = 1971
 |pages = 151–158
 |doi = 10.1145/800157.805047
 |language = engleză
 }}
* {{cite web
 |last = Dunne
 |first = P.E
 |title = An annotated list of selected NP-complete problems
 |publisher = COMP202, Dept. of Computer Science, {{Ill-wd|Q499510}}
 |url = http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html
 |accessdate = 2008-06-21
 |language = engleză
 }}
* {{cite web
 |last = Crescenzi
 |first = P.
 |author2 = Kann, V.
 |author3 = Halldórsson, M.
 |author4 = {{Ill-wd|Q92898|3=Karpinski, M.}}
 |author5 = {{Ill-wd|Q20994323|3=Woeginger, G}}
 |title = A compendium of NP optimization problems
 |publisher = KTH NADA, Stockholm
 |url = http://www.nada.kth.se/~viggo/problemlist/compendium.html
 |accessdate = 2008-06-21
 |language = engleză
 }}
* {{cite web
 |last = Dahlke
 |first = K
 |title = NP-complete problems
 |work = Math Reference Project
 |url = http://www.mathreference.com/lan-cx-np,intro.html
 |accessdate = 2008-06-21
 |language = engleză
 }}
* {{cite web |last = Karlsson |first = R |title = Lecture 8: NP-complete problems |publisher = Dept. of Computer Science, Lund University, Sweden |url = http://www.cs.lth.se/home/Rolf_Karlsson/bk/lect8.pdf |format = PDF |accessdate = 2008-06-21 |deadurl = yes |archiveurl = https://web.archive.org/web/20090419082030/http://www.cs.lth.se/home/Rolf_Karlsson/bk/lect8.pdf |archivedate = 19 aprilie 2009 }} 
* {{cite web
 |last = Sun
 |first = H.M
 |title = The theory of NP-completeness
 |publisher = Information Security Laboratory, Dept. of Computer Science, {{Ill-wd|Q43406}}, Hsinchu City, Taiwan
 |url = http://is.cs.nthu.edu.tw/course/2008Spring/cs431102/hmsunCh08.ppt
 |format = PPT
 |language = engleză
 |accessdate = 2008-06-21
 |archive-date = 2009-09-02
 |archive-url = https://web.archive.org/web/20090902082705/http://is.cs.nthu.edu.tw/course/2008Spring/cs431102/hmsunCh08.ppt
 |dead-url = yes
 }}
* {{cite web
 |last = Jiang
 |first = J.R
 |title = The theory of NP-completeness
 |publisher = Dept. of Computer Science and Information Engineering, {{Ill-wd|Q714891}}, Jhongli City, Taiwan
 |url = http://www.csie.ncu.edu.tw/%7Ejrjiang/alg2006/NPC-3.ppt
 |format = PPT
 |language = engleză
 |accessdate = 2008-06-21
 }}
* {{Cite book
 |last = Cormen
 |first = T.H.
 |authorlink = Thomas H. Cormen
 |author2={{Ill-wd|Q93028|3=Leiserson, C.E.}} |author3=[[Ronald L. Rivest|Rivest, R.L.]] |author4={{Ill-wd|Q2024396|3=Stein, C.}}
 |title = {{Ill-wd|Q1141518}}
 |edition = 2nd
 |year = 2001
 |publisher = MIT Press and McGraw-Hill
 |ISBN = 0-262-03293-7
 |language = engleză
 |chapter = Chapter 34: NP–Completeness
 |pages = 966–1021
}}
* {{Cite book
 |last = Sipser
 |first = M.
 |authorlink = Michael Sipser
 |title = Introduction to the Theory of Computation
 |year = 1997
 |publisher = PWS Publishing
 |chapter = Sections 7.4–7.5 (NP-completeness, Additional NP-complete Problems)
 |pages = 248–271
 |ISBN = 0-534-94728-X
}}
* {{Cite book
 |last = Papadimitriou
 |first = C.
 |authorlink = Christos Papadimitriou
 |title = Computational Complexity
 |edition = 1st
 |year = 1994
 |publisher = Addison Wesley
 |chapter = Chapter 9 (NP-complete problems)
 |language = engleză
 |pages = 181–218
 |ISBN = 0-201-53082-1
}}
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]
* [http://arxiv.org/abs/cs.CC/0210020 Tetris is Hard, Even to Approximate]
* [http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm Minesweeper is NP-complete!] {{Webarchive|url=https://web.archive.org/web/20061216121200/http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm |date=2006-12-16 }}
* {{Cite journal
 |last = Bern |first = Marshall
 |doi = 10.1002/net.3230200110
 |issue = 1
 |journal = Networks
 |pages = 109–120
 |title = Faster exact algorithms for Steiner trees in planar networks
 |volume = 20
 |year = 1990
 |ref = harv
 |language = engleză
 |postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->}}.
* {{Cite journal
 |last1 = Deĭneko |first1 = Vladimir G.
 |last2 = Klinz |first2 = Bettina
 |last3 = Woeginger |first3 = Gerhard J. |author3-link = Gerhard J. Woeginger
 |doi = 10.1016/j.orl.2005.04.013
 |issue = 3
 |journal = Operations Research Letters
 |pages = 269–274
 |title = Exact algorithms for the Hamiltonian cycle problem in planar graphs
 |volume = 34
 |year = 2006
 |ref = harv
 |language = engleză
 |postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->}}.
* {{Cite book
 |last1 = Dorn |first1 = Frederic
 |last2 = Penninkx |first2 = Eelko
 |last3 = Bodlaender |first3 = Hans L.  author3-link = Hans L. Bodlaender
 |last4 = Fomin |first4 = Fedor V.
 |doi = 10.1007/11561071_11
 |pages = 95–106
 |publisher = Springer-Verlag
 |series = Lecture Notes in Computer Science
 |title = Proc. 13th European Symposium on Algorithms (ESA '05)
 |volume = 3669
 |year = 2005
 |chapter = Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
 |ISBN = 978-3-540-29118-3
 |ref = harv
 |language = engleză
 |postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->}}.
* {{Cite journal
 |last1 = Lipton |first1 = Richard J. |author1-link = Richard J. Lipton
 |last2 = Tarjan |first2 = Robert E. |author2-link = Robert Tarjan
 |doi = 10.1137/0209046
 |journal = {{Ill-wd|Q7390263}}
 |pages = 615–627
 |title = Applications of a planar separator theorem
 |volume = 9
 |year = 1980
 |issue = 3
 |ref = harv
 |language = engleză
 |postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->}}.
{{refend}}

== Lectură suplimentară ==
{{refbegin}}
* {{Ill-wd|Q4054157}}, ''[http://arxiv.org/abs/quant-ph/0502072 NP-complete Problems and Physical Reality]'', ACM {{Ill-wd|Q3387984}} News, Vol. 36, No. 1. (March 2005), pp.&nbsp;30–52.
* {{Ill-wd|Q92922}}, ''[http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf The status of the P versus NP problem]'', {{Ill-wd|Q1120519}}, Vol. 52, No. 9. (2009), pp.&nbsp;78–86.
{{refend}}
[[Categorie:Clase de complexitate]]
[[Categorie:Optimizare]]