Vizualizare sursă pentru „Clasele de complexitate P și NP”

{{unsolved|informatică|Dacă corectitudinea soluției unei probleme este ușor de verificat, este problema și ușor de rezolvat?}}
[[Fișier:Complexity_classes.svg|miniatura|250x250px|Diagramă a claselor de complexitate, cu premisa că '''P'''&nbsp;≠&nbsp;'''NP'''. În această ipoteză, existența problemelor din '''NP''', dar care nu sunt nici '''P''' și nici '''NP'''-complete, a fost stabilită prin {{Ill-wd|Q1130846|3=teorema lui Ladner}}.<ref name="Ladner75">R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM, 22, pp. 151–171, 1975. </ref>]]
'''Problema claselor de complexitate P și NP''' este o mare [[Lista problemelor nerezolvate din informatică|problemă nerezolvată din informatică]]. Ca o definiție informală, ea este întrebarea dacă fiecare problemă ale cărei soluții pot fi verificate rapid de un calculator poate fi și rezolvată rapid de un calculator.  Esența ei a fost menționată pentru prima oară într-o scrisoare din 1956 scrisă de [[Kurt Gödel]] și adresată lui [[John von Neumann]].  Gödel a pus problema dacă o anumită problemă [[NP-completitudine|NP-completă]] poate fi rezolvată în [[Complexitate în timp|timp pătratic]] sau [[Complexitate în timp|liniar]].<ref>{{Citat revistă|nume=Hartmanis|prenume=Juris|an=|titlu=Gödel, von Neumann, and the P = NP problem|url=http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf|format=PDF|journal=Bulletin of the European Association for Theoretical Computer Science|volum=38|număr=|pagini=101–107}}</ref> Formularea exactă a problemei claselor de complexitate P și NP a fost introdusă în 1971 de către [[Stephen Cook]] în lucrarea sa „Complexitatea procedurilor de demonstrare a teoremelor”<ref>{{Citat carte|nume=Cook|prenume=Stephen|legătură-autor=Stephen Cook|an=1971|capitol=The complexity of theorem proving procedures|url-capitol=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047|titlu=Proceedings of the Third Annual ACM Symposium on Theory of Computing|pagini=151–158}}</ref> și este considerată a fi cea mai importantă problemă deschisă din domeniu.<ref>{{Citat revistă|nume=Fortnow|prenume=Lance|legătură-autor=Lance Fortnow|an=2009|titlu=The status of the '''P''' versus '''NP''' problem|url=http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|format=PDF|journal=Communications of the ACM|volum=52|număr=9|pagini=78–86|doi=10.1145/1562164.1562186|DOI=10.1145/1562164.1562186}}</ref> Este una dintre cele șapte {{Ill-wd|Q727000|3=probleme pentru Premiul Mileniului}} selectate de {{Ill-wd|Q857975}}, care oferă un premiu de 1.000.000 de dolari pentru prima soluție corectă.

Termenul informal ''rapid'', utilizat mai sus, se definește ca existența unui algoritm care rulează în [[Complexitate în timp|timp polinomial]]. Clasa generală de întrebări pentru care un algoritm poate da răspuns în timp polinomial se numește „clasa de complexitate P”, sau simplu „[[P (teoria complexității)|P]]”. Pentru unele probleme însă, nu există o metodă de a găsi rapid un răspuns, dar dacă unui calculator i se prezintă un posibil răspuns, el îl poate verifica rapid. Clasa de astfel de probleme care pot fi ''verificate'' în timp polinomial se numește '''[[NP (teoria complexității)|NP]]''', care înseamnă „timp nedeterminist polinomial”.

Fie problema sumei elementelor submulțimilor, un exemplu de problemă ușor de verificat, dar al cărui răspuns poate fi dificil de calculat. Dată fiind o mulțime de [[Număr întreg|numere întregi]], există vreo [[submulțime]] nevidă a ei ale cărei elemente au suma 0? De exemplu, există o submulțime a mulțimii <span class="nowrap"> {−2, −3, 15, 14, 7, −10} </span> ale cărei elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea <span class="nowrap"> {−2, −3, −10, 15} </span> are suma zero” și poate fi rapid verificat efectuând trei adunări; dar nu există niciun algoritm cunoscut care să găsească această submulțime în timp polinomial (există doar unul care îl găsește în timp exponențial, și care efectuează 2<sup>''n''</sup>-n-1 încercări). Un astfel de algoritm există doar dacă '''P'''&nbsp;=&nbsp;'''NP'''; deci această problemă este în '''NP''' (rapid verificabilă) dar nu neapărat în '''P''' (rapid rezolvabilă).

Soluția problemei '''P'''&nbsp;=&nbsp;'''NP''' ar determina dacă problemele ce se pot verifica în timp polinomial, ca problema sumei elementelor submulțimii, pot fi și rezolvate în timp polinomial. Dacă se dovedește că '''P'''&nbsp;≠&nbsp;'''NP''', ar însemna că există probleme din '''NP''' (cum ar fi problemele [[NP-completitudine|'''NP'''-complete]]) care sunt mai greu de calculat decât de verificat: ele nu pot fi rezolvate în timp polinomial, dar o soluție se poate verifica în timp polinomial.

Pe lângă importanța problemei în [[teoria calculabilității]], o dovadă în oricare sens ar avea profunde implicații în matematică, criptografie, algoritmică, [[inteligență artificială]], [[teoria jocurilor]], procesarea multimedia, [[Filozofie|filosofie]], [[economie]] și în multe alte domenii.

== Context ==
Relația între [[Clasă de complexitate|clasele de complexitate]] '''P''' și '''NP''' este studiată în [[Teoria complexității|teoria complexității computaționale]], ramura [[Teoria computației|teoriei computației]] care tratează resursele de calcul necesare pentru rezolvarea unei probleme date. Cele mai comune astfel de resurse sunt timpul (numărul de pași necesari rezolvării unei probleme) și spațiul (cantitatea de memorie necesară rezolvării unei probleme).

În astfel de analize este nevoie de un model de calculator pentru care se face analiza. De regulă, aceste modele presupun că calculatorul este ''{{Ill-wd|Q5265707|3=determinist}}'' (date fiind o stare a calculatorului și un set de intrări, există o singură acțiune posibilă pe care o poate efectua calculatorul) și ''secvențial'' (efectuează acțiunile una după alta).

În această teorie, clasa '''P''' constă din acele ''{{Ill-wd|Q3262192|3=probleme ale deciziei}}'' (definite [[#Definiții formale|mai jos]]) care pot fi rezolvate pe o mașină deterministă secvențială într-un timp [[Polinom|polinomial]] în funcție de dimensiunea intrării; clasa '''[[NP (teoria complexității)|NP]]''' constă din acele probleme de decizie ale căror soluții pozitive pot fi verificate în [[Complexitate în timp|timp polinomial]] date fiind informațiile corecte, sau echivalent, a cărei soluție poate fi găsită în timp polinomial pe o mașină [[Mașină Turing nedeterministă|nedeterministă]].<ref>Sipser, Michael: ''Introduction to the Theory of Computation, Second Edition, International Edition'', page 270. </ref> Evident, '''P''' ⊆ '''NP'''. Cea mai mare problemă deschisă în informatica teoretică privește relația dintre aceste două clase:
: Este '''P''' echivalent cu '''NP'''?
Într-un sondaj efectuat în 2002 pe 100 de cercetători, 61 credeau că răspunsul este nu, 9 credeau că este da, și 22 nu erau siguri; 8 credeau că întrebarea s-ar putea să fie {{Ill-wd|Q2705017|3=independentă}} de axiomele actual acceptate și astfel imposibil de demonstrat într-un sens sau altul.<ref name="poll">{{Citat revistă|nume=William I. Gasarch|legătură-autor=William Gasarch|titlu=The P=?NP poll.|journal=SIGACT News|volum=33|număr=2|pagini=34–47|dată=June 2002|url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/1052796.1052804|DOI=10.1145/1052796.1052804|format=PDF|access-date=29 December 2008|accessdate=29 December 2008}}</ref>

În 2012, 10 ani mai târziu, sondajul a fost repetat. Numărul cercetătorilor care au răspuns a fost 151: 126 (83%) credeau că răspunsul este nu, 12 (9%) credeau că este da, 5 (3%) credeau că problema este independentă de axiomele actualmente acceptate și deci imposibil de rezolvat, 8 (5%) au spus că fie nu știu, fie că nu vor ca problema să fie rezolvată sau ca răspunsul să fie da.<ref name="poll2">{{Citat revistă|nume=William I. Gasarch|legătură-autor=William Gasarch|titlu=The Second P=?NP poll|journal=SIGACT News|volum=74|url=http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf|format=PDF}}</ref>

== NP-completitudinea ==
[[Fișier:P_np_np-complete_np-hard.svg|dreapta|miniatura|[[Diagramă Euler]] pentru seturile de probleme '''[[P (teoria complexității)|P]]''', '''[[NP (teoria complexității)|NP]]''', '''NP'''-complete și '''NP'''-tari]]
Pentru a aborda problema '''P''' = '''NP''', este util conceptul de '''NP'''-completitudine. Problemele '''NP'''-complete sunt o mulțime de probleme la care poate fi redusă orice altă problemă '''NP''' în timp polinomial, și ale căror soluții pot fi verificate în timp polinomial. Adică, orice problemă '''NP''' poate fi ușor transformată în oricare dintre problemele '''NP'''-complete. Informal, o problemă '''NP'''-completă este o problemă '''NP''' care este cel puțin la fel de „grea” ca și orice altă problemă din '''NP'''.

Problemele '''NP'''-tari (sau NP-hard) sunt cele care sunt cel puțin la fel de grele ca problemele NP, adică toate problemele '''NP''' pot fi reduse (în timp polinomial) la ele. Problemele '''NP'''-hard nu sunt neapărat în '''NP''', adică nu este nevoie ca ele să aibă soluții verificabile în timp polinomial.

De exemplu, {{Ill-wd|Q875276|3=problema satisfiabilității booleene}} este '''NP'''-completă conform {{Ill-wd|Q377276|3=teoremei Cook–Levin}}, deci ''orice'' instanță a ''oricărei'' probleme din '''NP''' poate fi transformată mecanic în timp polinomial într-o instanță a problemei satisfiabilității booleene. Problema satisfiabilității este una din multele astfel de probleme '''NP'''-complete. Dacă orice problemă '''NP'''-completă este în '''P''', atunci ar rezulta că '''P''' = '''NP'''. Din păcate, s-a demonstrat că multe probleme importante sunt '''NP'''-complete și nu se cunoaște niciun algoritm rapid pentru oricare dintre ele.

Doar pe baza definiției nu este evident că există probleme '''NP'''-complete; dar o problemă '''NP'''-completă trivială ar putea fi formulată astfel: dată fiind o descriere a unei mașini Turing M care în mod garantat se oprește în timp polinomial, există o intrare de dimensiuni polinomiale pe care M le va accepta?<ref name="Scott">{{Citat web|author=Scott Aaronson|titlu=PHYS771 Lecture 6: P, NP, and Friends|url=http://www.scottaaronson.com/democritus/lec6.html|accessdate=27 august 2007}}</ref> Ea este în '''NP''' deoarece (dată fiind o intrare) este simplu de verificat dacă M acceptă intrarea simulând funcționarea mașinii Turing M; este '''NP'''-completă deoarece verificatorul oricărei instanțe de problemă din '''NP''' poate fi codificat ca mașină Turing M de timp polinomial care primește ca intrare soluția de verificat. Apoi întrebarea dacă instanța de problemă primește un răspuns „da” sau un răspuns „nu” se determină prin verificarea existenței unei intrări valide.

Prima problemă naturală demonstrată a fi '''NP'''-completă a fost {{Ill-wd|Q875276|3=problema satisfiabilității booleene}}. Cum s-a arătat mai sus, aceasta este {{Ill-wd|Q377276|3=teorema Cook–Levin}}; demonstrația că satisfiabilitatea este '''NP'''-completă conține detalii tehnice despre mașinile Turing așa cum sunt ele legate de definiția clasei '''NP'''. După ce s-a demonstrat că această problemă este '''NP'''-completă, însă, {{Ill-wd|Q1197709|3=demonstrația prin reducere}} a furnizat o manieră mai simplă de a arăta că multe alte probleme sunt '''NP'''-complete, inclusiv {{Ill-wd|Q1154420|3=problema sumei elementelor submulțimilor}} discutată anterior. Astfel, o clasă vastă de probleme aparent fără legătură unele cu altele sunt toate reductibile unele la altele, și, într-un anume sens, sunt „aceeași problemă”.

== Probleme mai grele ==
Deși nu se cunoaște dacă '''P''' = '''NP''', se cunosc probleme care sunt în afara '''P'''. Un număr de probleme  succinte (probleme care nu operează pe intrări normale, ci pe o descriere computațională a intrării) sunt cunoscute a fi {{Ill-wd|Q1276570|3='''EXPTIME'''-complete}}. Pentru că se poate demonstra că '''P''' ≠ '''{{Ill-wd|Q1276570}}''', aceste probleme sunt în afara '''P''', și deci necesită timp mai mult decât polinomial. În fapt, prin {{Ill-wd|Q5251122}}, ele nu pot fi rezolvate în mod semnificativ mai rapid decât în timp exponențial. Printre exemple se numără găsirea unei strategii perfecte în jocul de șah (pe o tablă ''N'' × ''N'')<ref name="Fraenkel1981">{{Citat revistă|nume={{Ill-wd|Q541206}} and D. Lichtenstein|titlu=Computing a perfect strategy for n×n chess requires time exponential in n|journal=J. Comb. Th. A|număr=31|an=1981|pagini=199–214}}</ref> și alte jocuri de masă.<ref>{{Citat web|titlu=Computational Complexity of Games and Puzzles|url=http://www.ics.uci.edu/~eppstein/cgt/hard.html|author={{Ill-wd|Q3017847}}}}</ref>

Problema de a decide adevărul unei afirmații în {{Ill-wd|Q956059|3=aritmetica Presburger}} necesită și mai mult timp. Fischer și [[Michael Rabin|Rabin]] au demonstrat în 1974 că fiecare algoritm care decide adevărul unei afirmații Presburger are un timp de execuție de cel puțin <math>2^{2^{cn}}</math> pentru o constantă ''c''. Aici, ''n'' este lungimea afirmației Presburger. Prin urmare, se știe că problema are nevoie de un timp mai mult decât exponențial pentru a fi rezolvată. Chiar și mai grele sunt{{Ill-wd|Q3502995|3= problemele indecidabile}}, cum ar fi {{Ill-wd|Q622849|3=problema opririi}}. Ele nu pot fi complet rezolvate de un algoritm, în sensul că pentru orice algoritm există cel puțin o intrare pentru care algoritmul nu va produce răspunsul corect; el va produce fie răspunsul greșit, fie se va opri fără a da un răspuns concludent, sau în caz contrar, se va executa fără a se opri și fără a produce vreun răspuns.

== Problemele din NP despre care nu se știe dacă sunt în P sau NP-complete ==
S-a demonstrat de către Ladner că dacă '''P''' ≠ '''NP''' atunci există probleme în '''NP''' care nu sunt nici în '''P''' nici '''NP'''-complete.<ref name="Ladner75">R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM, 22, pp. 151–171, 1975. </ref> Astfel de probleme se numesc probleme '''NP'''-intermediare. {{Ill-wd|Q3738036|3=Problema izomorfismului grafurilor}}, [[Logaritm discret|problema logaritmului discret]] și [[Factorizarea întregilor|problema factorizării numerelor întregi]] sunt exemple de probleme considerate a fi '''NP'''-intermediare. Acestea sunt unele dintre puținele probleme '''NP''' despre care nu se știe dacă sunt în '''P''' sau '''NP'''-complete.

Problema izomorfismului grafurilor este problema computațională de a determina dacă două [[Graf|grafuri]] finite sunt [[Izomorfism de grafuri|izomorfe]]. O importantă problemă nerezolvată în teoria complexității este dacă problema izomorfismului grafurilor este în '''P''', '''NP'''-completă, sau '''NP'''-intermediară. Răspunsul nu este cunoscut, dar se crede că problema cel puțin nu este '''NP'''-completă.<ref name="AK06">{{Citat revistă|prenume=Vikraman|nume=Arvind|prenume2=Piyush P.|nume2=Kurur|titlu=Graph isomorphism is in SPP|journal=Information and Computation|volum=204|număr=5|an=2006|pagini=835–852|doi=10.1016/j.ic.2006.02.002|DOI=10.1016/j.ic.2006.02.002|postscript=.}}</ref> Dacă izomorfismul grafurilor ar fi '''NP'''-completă, {{Ill-wd|Q2103021|3=ierarhia timpului polinomial}} s-ar plia la al doilea nivel.<ref>{{Citat revistă|nume=Schöning|prenume=Uwe|legătură-autor=Uwe Schöning|an=|titlu=Graph isomorphism is in the low hierarchy|url=|journal=Proceedings of the 4th Annual {{Ill-wd|Q7661892}}|volum=1987|număr=|pagini=114–124|doi=10.1007/bfb0039599|DOI=10.1007/bfb0039599}}</ref><ref>{{Citat revistă|nume=Schöning|prenume=Uwe|legătură-autor=Uwe Schöning|an=1988|titlu=Graph isomorphism is in the low hierarchy|url=|journal=Journal of Computer and System Sciences|volum=37|număr=|pagini=312–323|doi=10.1016/0022-0000(88)90010-4|DOI=10.1016/0022-0000(88)90010-4}}</ref> Deoarece se crede că ierarhia polinomială nu se pliază la niciun nivel finit, se crede că izomorfismul grafurilor nu este o problemă '''NP'''-completă. Cel mai bun algoritm pentru această problemă, datorat lui {{Ill-wd|Q92845}} și {{Ill-wd|Q10561835}}, a rulat timp de 2<sup>O(√''n''log(''n''))</sup> pentru un graf cu ''n'' noduri.

[[Factorizarea întregilor|Problema factorizării numerelor întregi]] este problema calculului [[Factorizarea întregilor|descompunerii în factori primi]] a unui număr întreg dat. Formulată ca o problemă de decizie, ea este problema de a decide dacă intrarea are un factor prim mai mic decât ''k''. Nu se cunoaște niciun algoritm eficient de factorizare a numerelor întregi, și acest fapt stă la baza celor mai multe sisteme criptografice moderne, cum ar fi algoritmul [[RSA]]. Problema factorizarea numerelor întregi problemă este în '''NP''' și în '''{{Ill-wd|Q955748}}''' (și chiar în '''UP''' și '''co-UP'''<ref>Lance Fortnow. </ref>). Dacă problema este '''NP'''-completă, ierarhia polinomială se va plia la primul nivel (de exemplu, '''NP''' = '''co-NP'''). Cel mai cunoscut algoritm pentru factorizarea numerelor întregi este {{Ill-wd|Q140770|3=ciurul câmpurilor de numere generalizat}}, al cărui timp de rulare este

:<math>O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right )</math>

la factorizarea unui număr întreg pe'' n ''biți. Cu toate acestea, cel mai cunoscut {{Ill-wd|Q2623817|3=algoritm cuantic}} pentru această problemă, {{Ill-wd|Q940334|3=algoritmul lui Shor}}, rulează în timp polinomial. Din păcate, acest fapt nu spune prea multe despre clasa de problemă necuantică din care face parte factorizarea.

== P înseamnă „ușor”? ==
[[Fișier:KnapsackEmpComplexity.GIF|miniatura|310x310px|Graficul prezintă timpul de rulare (o medie a 100 de cazuri în ms, folosind un Pentium III la 933 MHz) în raport cu dimensiunea problemei pentru problema rucsacului rezolvată printr-o implementare a unui algoritm specializat {{lang|en|state-of-the-art}}. Curba de regresie pătratică sugerează că complexitatea algoritmică empirică pentru cazuri cu 50&ndash;10.000 de variabile este O((log(''n''))<sup>2</sup>).<ref name="Pisinger2003">Pisinger, D. 2003. </ref>]]
Toată discuția de mai sus pornește de la presupunerea că '''P''' înseamnă „ușor” și „nu în '''P”''' înseamnă „greu”, o presupunere cunoscută sub numele de ''{{Ill-wd|Q5138877|3=teza lui Cobham}}''. Este o ipoteză comună și de o acuratețe rezonabilă din teoria complexității; cu toate acestea, ea are unele limitări.

În primul rând, nu este întotdeauna adevărată în practică. Un algoritm teoretic în timp polinomial poate avea factori constanți sau exponenți extrem de mari, ceea ce l-ar face nepractic. Pe de altă parte, chiar dacă o problemă este dovedit a fi '''NP'''-completă, și chiar dacă '''P''' ≠ '''NP''', încă ar putea exista abordări eficiente pentru rezolvarea problemei pe cazurile practice. Există algoritmi pentru multe '''NP'''-complete, cum ar fi [[Problema rucsacului|problema rucsacului]], [[Problema comis-voiajorului|problema comis-voiajorului]] și {{Ill-wd|Q875276|3=problema satisfiabilității booleene}}, care pot rezolva optim multe cazuri din lumea reală asociate lor într-un timp rezonabil. {{Ill-wd|Q4828244|3=Complexitatea cazului mediu}} (timp vs dimensiunea problemei) a acestui fel de algoritmi poate fi surprinzător de scăzută. Un exemplu este [[Algoritm simplex|algoritmul simplex]] din [[Programare liniară|programarea liniară]], care funcționează surprinzător de bine în practică; în ciuda faptului că are complexitate exponențială pe cel mai rău caz, el rulează pe picior de egalitate cu cei mai cunoscuți algoritmi în timp polinomial.<ref>{{Citat carte|nume=Gondzio|prenume=Jacek|nume2=Terlaky|prenume2=Tamás|capitol=3 A computational view of interior point methods|titlu=Advances in linear and integer programming|pagini=103–144|nume-editor=J.&nbsp;E. Beasley|locul-publicării=New York|editură=Oxford University Press|an=1996|serie=Oxford Lecture Series in Mathematics and its Applications|volum=4|url=http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps|ref=harv|id=[http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps Postscript file at website of Gondzio] and [http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-94-73.ps.gz at McMaster University website of Terlaky]}}</ref>

În al doilea rând, există tipuri de calcule care nu sunt conforme cu modelul mașinii Turing pe care sunt definite clasele '''P''' și '''NP''', cum ar fi [[Calculator cuantic|calculul cuantic]] și {{Ill-wd|Q583461|3=algoritmii probabilistici}}.

== Motive pentru a crede că P ≠ NP ==
Potrivit sondajelor,<ref name="poll"/><ref>{{Citat revistă|titlu='''P''' vs. '''NP''' poll results|journal=Communications of the ACM|dată=May 2012|volum=55|număr=5|pagină=10|prenume=Jack|nume=Rosenberger|url=http://mags.acm.org/communications/201205?pg=12}}</ref> mulți informaticieni cred că '''P''' ≠ '''NP'''. Un motiv cheie pentru această credință este că, după zeci de ani de studiu al acestor probleme, nimeni nu a fost capabil să găsească un algoritm în timp polinomial pentru vreuna din cele peste 3000 de probleme importante '''NP'''-complete cunoscute (a se vedea {{Ill-wd|Q3244933|3=Lista de probleme '''NP'''-complete}}). Acești algoritmi au fost căutați cu mult timp înainte de definirea conceptului de '''NP'''-completitudine ([[Cele 21 de probleme NP-complete ale lui Karp|Cele 21 de probleme '''NP'''-complete ale lui Karp]], printre primele găsite, erau toate problemele bine-cunoscute existente deja la momentul la care s-au dovedit a fi '''NP'''-complete). În plus, rezultatul '''P''' = '''NP''' ar implica multe alte rezultate uimitoare, care sunt în prezent considerate a fi false, cum ar fi '''NP''' = '''{{Ill-wd|Q955748}}''' și '''P''' = '''{{Ill-wd|Q1063380|3=PH}}'''.

Se susține și intuitiv că existența unor probleme care sunt greu de rezolvat, dar ale căror soluții sunt ușor de verificat se potrivește cu experiența din lumea reală.<ref>{{Citat web-LUA|url=http://scottaaronson.com/blog/?p=122|author=Scott Aaronson|titlu=Reasons to believe}}, punctul 9</ref>
{{quote|Dacă '''P''' <nowiki>=</nowiki> '''NP''', atunci lumea ar fi un loc profund diferit de ceea ce presupunem noi de regulă că este. Nu ar exista valoare specială în „salturi creative”, nu ar exista un ecart fundamental între rezolvarea unei probleme și recunoașterea soluției odată găsite.| {{Ill-wd|Q4054157}}, [[MIT]]}}

Pe de altă parte, unii cercetători cred că încrederea că '''P''' ≠ '''NP''' este exagerată și că cercetătorii ar trebui să caute demonstrații că '''P''' = '''NP''' . De exemplu, în anul 2002, s-au făcut următoarele afirmații:<ref name="poll"/>
{{quote|Principalul argument în favoarea ideii că '''P'''&nbsp;≠&nbsp;'''NP''' este lipsa totală de progres fundamental în zona căutării exhaustive. Acesta este, după părerea mea, un argument foarte slab. Spațiul algoritmilor este foarte mare și suntem doar la începutul explorării lui. [...] Rezolvarea [[Marea teoremă a lui Fermat|Ultimei Teoreme a lui Fermat]] arată și că întrebările foarte simple pot primi un răspuns doar din partea unor teorii foarte profunde.|{{Ill-wd|Q1585964}}, {{Ill-wd|Q842909}}}}
{{quote|Atașamentul față de o speculație nu este un ghid bun pentru planificarea cercetării. Trebuie să se cerceteze întotdeauna ambele direcții ale fiecărei probleme. Prejudecata i-a împiedicat pe mulți matematicieni celebri să rezolve probleme celebre ale căror soluții erau opusul așteptărilor lor, deși își dezvoltaseră toate metodele necesare.|{{Ill-wd|Q500281}}, [[Cornell University]]}}

== Consecințele unei soluții ==
Unul dintre motivele pentru care problema atrage atât de multă atenție îl constituie consecințele unui răspuns. În orice sens ar fi răspunsul, teoria ar face un salt enorm, iar consecințele practice ar fi epocale.

=== P = NP ===
O demonstrație că '''P''' = '''NP''' ar putea avea uimitoare consecințe practice, dacă dovada conduce la metode eficiente pentru rezolvarea unora dintre cele mai importante probleme din '''NP'''. Este de asemenea posibil ca o dovadă să nu conducă direct la metode eficiente, dacă de exemplu dovada este {{Ill-wd|Q3044470|3=neconstructivă}}, sau dacă dimensiunea polinomului de încadrare este prea mare pentru a fi eficientă în practică. Consecințele, atât pozitive, cât și negative, rezultă deoarece diverse probleme '''NP'''-complete sunt fundamentale în mai multe domenii.

Criptografia, de exemplu, se bazează pe faptul că anumite probleme sunt dificil de rezolvat. O soluție constructivă și eficientă<ref group="lower-alpha"> depinde de detalii exact cât de eficientă trebuie să fie o soluție ca să reprezinte o amenințare pentru criptografie. O soluție de complexitate <math>\Omega(N^2)</math> sau mai bună și cu un [[termen constant]] rezonabil ar fi dezastruoasă. Pe de altă parte, o soluție care este <math>\Omega(N^4)</math> sau mai rea în aproape toate cazurile nu ar pune niciun pericol practic imediat.</ref> pentru o problemă '''NP'''-completă, cum ar fi {{Ill-wd|Q875276|3=3-SAT}},  ar distruge majoritatea criptosistemelor existente, între care:
* [[Criptografie asimetrică|criptografia cu chei publice]],<ref>Vezi {{Citat revistă|titlu=Hard instance generation for SAT|nume=Horie, S. and Watanabe, O.|journal=Algorithms and Computation|pagini=22–31|an=1997|publisher=Springer|bibcode=1998cs........9117H|nume2=Watanabe|doi=10.1007/3-540-63890-3_4|DOI=10.1007/3-540-63890-3_4|series=Lecture Notes in Computer Science|isbn=978-3-540-63890-2|ISBN=978-3-540-63890-2|volum=1350}}</ref> un fundament pentru multe aplicații de securitate, cum ar fi tranzacțiile financiare prin Internet; și
* {{Ill-wd|Q327675|3=cifrurile simetrice}} , cum ar fi [[AES]] sau [[3DES]],<ref>Vezi, de exemplu, {{Citat revistă|titlu=Logical cryptanalysis as a SAT problem|nume=Massacci, F. and Marraro, L.|journal=Journal of Automated Reasoning|volum=24|număr=1|pagini=165–203|an=2000|publisher=Springer|id={{citeseerx|10.1.1.104.962}}|ID={{citeseerx|10.1.1.104.962}}|doi=10.1023/A:1006326723002|DOI=10.1023/A:1006326723002}}</ref> folosite pentru criptarea datelor în comunicații.
* {{Ill-wd|Q720931|3=funcțiile unidirecționale}} utilizate în [[Funcție hash|hash-urile criptografice]]. Problema găsirii unei pre-imagini al cărui hash este anumită valoare<ref>Find a message''M'' that when hashed by the function ''H()'' gives a digest ''h'', or ''H(M)=h''</ref> trebuie să fie dificilă pentru ca hash-urile să fie utile, și în mod ideal, ar trebui să solicite timp exponențial. Cu toate acestea, dacă P=NP, atunci găsirea unei pre-imagini M s-ar putea face în timp polinomial, prin reducere la SAT.<ref>{{Citat știre|title=Inversion attacks on secure hash functions using SAT solvers|nume=De, Debapratim and Kumarasubramanian, Abishek and Venkatesan, Ramarathnam|pages=377–382|an=2007|publisher=Springer}}</ref>
Acestea ar trebui să fie modificate sau înlocuite cu soluții {{Ill-wd|Q3510462|3=informatic sigure}} care nu se bazează inerent pe echivalența P-NP.

Pe de altă parte, sunt enorme consecințe pozitive care ar rezulta din transformarea unor probleme greu de rezolvat din punct de vedere matematic în probleme tratabile. De exemplu, multe probleme în {{Ill-wd|Q194292|3=cercetarea operațională}} sunt '''NP'''-complete, cum ar fi unele tipuri de {{Ill-wd|Q6042592|3=probleme cu numere întregi}} și [[Problema comis-voiajorului|problema comis-voiajorului]]. Soluții eficiente la aceste probleme ar avea implicatii enorme pentru logistică. Multe alte probleme importante, cum ar fi unele probleme de {{Ill-wd|Q899656|3=predicția structurilor proteinelor}}, sunt, de asemenea, '''NP'''-complete;<ref name="Berger">{{Citat revistă|nume={{Ill-wd|Q18808526|3=Berger B}}, {{Ill-wd|Q5424058|3=Leighton T}}|titlu=Protein folding in the hydrophobic-hydrophilic (HP) model is '''NP'''-complete|journal=J. Comput. Biol.|volum=5|număr=1|pagini=27–40|an=1998|pmid=9541869|PMID=9541869|doi=10.1089/cmb.1998.5.27|DOI=10.1089/cmb.1998.5.27}}</ref> dacă aceste probleme ar fi rezolvabile eficient, s-ar putea stimula progrese considerabile în domeniul științelor vieții și biotehnologiei.

Dar astfel de modificări pălesc în importanță în raport cu revoluția pe care ar produce-o o metodă eficientă pentru rezolvarea problemelor '''NP'''-complete în matematică. În primele sale gânduri despre complexitatea computațională, Gödel observa că o metodă mecanică care ar putea rezolva orice problemă ar revoluționa matematica:<ref>Istoria acestei scrisori și traducerea ei din {{Citat web|titlu=The History and Status of the P versus NP question|author=Michael Sipser|url=http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf|accessdate=2016-09-01|archive-date=2014-02-02|archive-url=https://web.archive.org/web/20140202095503/http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf|dead-url=yes}}</ref><ref>{{Citat web|url=http://www.research.att.com/techdocs/TD_100899.pdf|titlu=A Brief History of NP-Completeness, 1954–2012|author=David S. Johnson}}</ref>

{{quote|Dacă chiar ar exista o mașină cu φ(n) ∼ k ⋅ n (sau chiar ∼ k ⋅ n<sup>2</sup>), aceasta ar avea consecințe de cea mai mare importanță. Și anume, ar însemna evident că în ciuda indecidabilității [[Problema deciziei|problemei deciziei]], munca mentală a unui matematician ce privește probleme Da-sau-Nu ar putea fi complet înlocuită de o mașină. În definitiv, va fi nevoie doar să alegi numărul n să fie atât de mare încât atunci când mașina nu dă un rezultat, atunci nu are sens să te mai gândești la problemă.}}

În mod similar, [[Stephen Cook]] spune<ref name="Official Problem Description">{{Citat revistă|nume=Cook|prenume=Stephen|legătură-autor=Stephen Cook|titlu=The '''P''' versus '''NP''' Problem|publisher={{Ill-wd|Q857975}}|dată=April 2000|url=http://www.claymath.org/sites/default/files/pvsnp.pdf|access-date=18 October 2006|accessdate=18 October 2006|archive-date=2015-09-04|archive-url=https://web.archive.org/web/20150904090304/http://www.claymath.org/sites/default/files/pvsnp.pdf|dead-url=yes}}</ref>
{{quote|...ar transforma matematica permițând unui calculator să găsească o demonstrație formală pentru orice teoremă care are demonstrație de o lungime rezonabilă, întrucât demonstrațiile formale pot fi verificate ușor în timp polinomial. Probleme ce ar putea fi astfel rezolvate, de exemplu, ar fi toate Problemele Mileniului de la Institutul Clay.}}

Matematicieni cercetători își petrec întregile lor cariere încercând să demonstreze teoreme, și unele demonstrații au fost găsite la decenii sau chiar secole după ce au fost enunțate problemele, de exemplu, [[Marea teoremă a lui Fermat|ultima teoremă a lui Fermat]] a fost demonstrată la peste trei secole de la enunțare. O metodă care ar găsi în mod garantat demonstrația unor teoreme, dacă există una de dimensiune „rezonabilă”, ar pune în esență capăt acestei lupte.

[[Donald E. Knuth|Donald Knuth]] a declarat că el a ajuns să creadă că P = NP, dar este rezervat cu privire la impactul unei posibile dovezi:<ref>{{Citat web|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.rss_f=Article&WT.rss_a=Twenty%20Questions%20for%20Donald%20Knuth&WT.rss_ev=a|titlu=Twenty Questions for Donald Knuth|date=20 mai 2014|lucrare=informit.com|work=informit.com|publisher={{Ill|en|InformIT}}|nume=Knuth|last=Knuth|first=Donald E.|authorlink=Donald Knuth|accessdate=20 July 2014}}</ref>
{{quote|1=[...] Nu cred că egalitatea P = NP se va dovedi utilă chiar dacă este demonstrată, deoarece o astfel de demonstrație va fi aproape sigur neconstructivă.}}

=== P ≠ NP ===
O demonstrație că '''P''' ≠ '''NP''' nu ar avea beneficiile computaționale practice ale unei demonstrații că '''P''' = '''NP''', dar ar reprezenta, totuși, un progres foarte important în teoria complexității computaționale și ar oferi îndrumare pentru cercetările viitoare. Aceasta ar permite să se arate în mod formal că multe probleme comune nu pot fi rezolvate eficient, astfel încât atenția cercetătorilor să se poată axa pe soluții parțiale sau pe soluțiile altor probleme. Din cauza convingerii larg răspândite că '''P''' ≠ '''NP''', o mare parte din această schimbare a avut deja loc.<ref>{{Citat revistă|titlu=The Heuristic Problem-Solving Approach|nume=L. R. Foulds|journal={{Ill-wd|Q6296171}}|volum=34|număr=10|dată=October 1983|pagini=927–934|jstor=2580891|JSTOR=2580891|doi=10.2307/2580891|DOI=10.2307/2580891}}</ref>

De asemenea, '''P''' ≠ '''NP''' lasă încă deschisă chestiunea {{Ill-wd|Q4828244|3=complexității pe cazul mediu}} a problemelor grele din '''NP'''. De exemplu, este posibil ca SAT să necesite timp exponențial în cel mai rău caz, dar că aproape toate cazurile selectate aleatoriu să fie eficient rezolvabile. {{Ill-wd|Q7381584}} a descris cinci „lumi” ipotetice, care ar putea duce la diferite rezoluții posibile pentru chestiunea complexității cazului mediu.<ref>R. Impagliazzo, [http://cseweb.ucsd.edu/~russell/average.ps "A personal view of average-case complexity,"] sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995</ref> Acestea variază de la „Algorithmica”, unde '''P''' = '''NP''' și probleme cum ar fi SAT pot fi rezolvate în mod eficient în toate cazurile, până la „Cryptomania”, unde '''P''' ≠ '''NP''' și se generează ușor probleme grele din afara '''P''', existând și trei posibilități intermediare reflectând diferite posibile distribuții ale dificultăți între cazuri de probleme '''NP-hard'''.„Lumea” în care '''P''' ≠ '''NP''' dar toate problemele din '''NP''' sunt maleabile în cazul mediu este numit „Heuristica” în articol. Un workshop ținut la [[Universitatea Princeton]] în 2009 a studiat starea celor cinci lumi.<ref>{{Citat web|url=http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/|titlu=Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds"|date=|accessdate=|publisher=|nume=|last=|first=|archiveurl=https://web.archive.org/web/20131115034042/http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/|archivedate=2013-11-15}}</ref>

== Rezultate despre dificultatea demonstrației ==
Deși problema '''P''' = '''NP'''? în sine rămâne deschisă, în ciuda premiului de un milion de dolari și a uriașei munci de cercetare dedicate, eforturile de a rezolva problema au condus la mai multe tehnici noi. În special, unele dintre cele mai fructuoase cercetări legate de '''P''' = '''NP''' a fost demonstrația faptului că tehnicile existente de demonstrație nu sunt suficient de puternice pentru a răspunde la întrebare, sugerând astfel că sunt necesare abordări inovatoare.

Ca o dovadă în plus pentru dificultatea problemei, în esență, toate tehnicile cunoscute de demonstrație din [[teoria complexității]] se încadrează în una dintre următoarele clasificări, dintre care fiecare se știe că este insuficientă pentru a dovedi că '''P''' ≠ '''NP''':
{| class="wikitable" style="margin-bottom: 10px; background-image: none; background-position: 0% 0%; background-repeat: repeat;"
!Clasificare
!Definiție
|-
|Demonstrații prin relativizare
|Să ne imaginăm o lume în care fiecărui algoritm îi este permis să facă interogări la o subrutină fixă numită {{Ill-wd|Q1143357|3=oracol}}, și timpul de funcționare al oracolului nu este calculat în timpul de execuție al algoritmului. Cele mai multe demonstrații (mai ales cele clasice) se aplică în mod uniform într-o lume cu oracole, indiferent ce fac aceste oracle. Aceste dovezi sunt numite ''prin'' ''relativizare''. În 1975, Baker, Gill, și {{Ill-wd|Q1395607|3=Solovay}} au arătat că '''P''' = '''NP''' în raport cu unele oracole, în timp ce '''P''' ≠ '''NP''' în raport cu alte oracole.<ref>T. P. Baker, J. Gill, R. Solovay. </ref> Întrucât demonstrațiile prin relativizare pot lămuri doar afirmații care sunt uniform adevărate în raport cu toate oracolele posibile, aceasta a demonstrat că tehnicile prin relativizare nu pot rezolva '''P''' = '''NP'''.
|-
|{{Ill-wd|Q6980761|3=Demonstrații naturale}}
|În 1993, {{Ill-wd|Q93019}} și {{Ill-wd|Q93146}} au definit o clasă generală de tehnici de demonstrație pentru limita inferioară a complexității circuitelor, denumite ''{{Ill-wd|Q6980761|3=demonstrații naturale}}''. La momentul respectiv, toate limitele inferioare erau naturale, și complexitatea circuitelor a fost considerată o abordare foarte promițătoare pentru rezolvarea problemei '''P''' = '''NP'''. Cu toate acestea, Razborov și Rudich au arătat că, dacă există {{Ill-wd|Q720931|3=funcții unidirecționale}}, atunci nicio demonstrație naturală nu poate distinge între '''P''' și '''NP'''. Deși nu s-a demonstrat niciodată existența funcțiilor unidirecționale, cei mai mulți matematicieni cred că ele există, și o demonstrație a existenței sau a inexistenței lor ar fi o afirmație mult mai puternică decât cuantificarea '''P''' relativ la '''NP'''. Astfel, este puțin probabil ca demonstrațiile naturale singure să poată rezolva '''P''' = '''NP'''.
|-
|Demonstrații prin algebrizare
|După rezultatul Baker-Gill-Solovay, au fost folosite cu succes tehnici noi de demonstrație fără relativizare pentru a demonstra că {{Ill-wd|Q5973158|3=IP}} = {{Ill-wd|Q500716}}. Cu toate acestea, în 2008, {{Ill-wd|Q4054157}} și [[Avi Wigderson]] au arătat că principalul instrument tehnic folosit în demonstrația că '''IP''' = '''PSPACE''', cunoscut sub numele de ''aritmetizare'', este insuficient pentru a rezolva '''P''' = '''NP'''.<ref><cite class="citation conference">S. Aaronson and A. Wigderson (2008). </cite></ref>
|}
Aceste bariere sunt un alt motiv pentru care problemele '''NP'''-complete sunt utile: dacă un algoritm în timp polinomial poate fi găsit pentru o problemă '''NP'''-completă, acest lucru ar rezolva problema '''P''' = '''NP''' într-un mod care nu este exclus de rezultatele de mai sus.

Aceste bariere i-au condus pe unii informaticieni care să sugereze că problema '''P''' versus '''NP''' poate fi {{Ill-wd|Q2705017|3=independentă}} de sistemele axiomatice standard, cum ar fi [[Sistemul axiomatic Zermelo-Fraenkel]] (nu pot fi dovedite sau infirmate în cadrul acestora). Interpretarea unei independențe ar putea fi că fie nu există algoritm în timp polinomial pentru vreo problemă '''NP'''-completă, și o astfel de demonstrație se poate construit în (de exemplu) ZFC, sau că pot exista algoritmi în timp polinomial pentru problemele '''NP'''-complete, dar că este imposibil de demonstrat în ZFC că astfel de algoritmi sunt corecți.<ref>{{Citat web|url=http://www.scottaaronson.com/papers/pnp.pdf|first=Scott|nume=Aaronson|last=Aaronson|authorlink=Scott Aaronson|titlu=Is '''P''' Versus '''NP''' Formally Independent?|postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->}}</ref> Cu toate acestea, dacă poate fi demonstrat, folosind tehnici de genul celor care în prezent sunt cunoscute a fi aplicabile, că problema nu poate fi decisă nici chiar cu ipoteze mai slabe care extind {{Ill-wd|Q842755|3=axiomele Peano}} (PA) pentru aritmetica numerelor întregi, atunci ar exista în mod necesar algoritmi în timp cvasipolinomial pentru orice problemă din '''NP'''.<ref>{{Citat revistă|titlu=On the independence of P versus NP|prenume=Shai|nume=Ben-David|prenume2=Shai|nume2=Halevi|series=Technical Report|volum=714|publisher=Technion|an=1992|url=http://www.cs.technion.ac.il/~shai/ph.ps.gz|postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->|access-date=2016-09-01|archive-date=2015-03-09|archive-url=https://web.archive.org/web/20150309042450/http://www.cs.technion.ac.il/%7Eshai/ph.ps.gz|dead-url=yes}}</ref> Prin urmare, dacă am crede (ca majoritatea teoreticienilor complexității) că nu toate problemele din '''NP''' au algoritmi eficienți, ar rezulta că demonstrarea independenței folosind aceste tehnici nu poate fi posibilă. În plus, acest rezultat implică faptul că demonstrarea independenței față de axiomele Peano sau față de ZFC folosind tehnici cunoscute în prezent nu e mai ușoară decât demonstrarea existenței unor algoritmi eficienti pentru toate problemele din '''NP'''.

== Soluții propuse ==
În timp ce problema '''P''' versus '''NP''' este în general considerată nerezolvată,<ref>{{Citat web|author={{Ill-wd|Q1700964}}|url=http://www.nytimes.com/2009/10/08/science/Wpolynom.html|titlu=Prizes Aside, the P-NP Puzzler Has Consequences|lucrare=The New York Times|work=The New York Times|date=8 October 2009}}</ref> mulți amatori și unii cercetători profesioniști au susținut soluții. {{Ill-wd|Q20994323}} are o listă cuprinzătoare.<ref>{{Citat web|titlu=The P-versus-NP page|url=http://www.win.tue.nl/~gwoegi/P-versus-NP.htm|author=Gerhard J. Woeginger|authorlink=Gerhard J. Woeginger|accessdate=25 May 2014}}</ref> O demonstrație propusă în august 2010 că '''P''' ≠ '''NP''', de Vinay Deolalikar, cercetător de la {{Ill-wd|Q266936}}, [[Palo Alto, California|Palo Alto]], a primit atenție masivă pe Internet și în presă după ce a fost inițial descrisă ca „părând să fie o încercare relativ serioasă” de către doi specialiști de frunte.<ref name="NYT2010">{{Citat știre|nume=Markoff|prenume=John|title=Step 1: Post Elusive Proof. Step 2: Watch Fireworks.|url=http://www.nytimes.com/2010/08/17/science/17proof.html?_r=1|accessdate=20 September 2010|newspaper=The New York Times|data=16 august 2010}}</ref> Demonstrația a fost revizuit în mod public de către mediul academic,<ref>{{Citat web|url=http://michaelnielsen.org/polymath1/index.php?title=Deolalikar_P_vs_NP_paper|author={{Ill-wd|Q2000812}} wiki|titlu=Deolalikar's '''P''' vs '''NP''' paper}}</ref><ref>Science News, [http://www.sciencenews.org/index/generic/activity/view/id/63252/title/Crowdsourcing_peer_review "Crowdsourcing peer review"]</ref> și {{Ill-wd|Q93057}}, un expert în domeniu, a subliniat două erori posibil fatale ale demonstrației.<ref>{{Citat web|titlu=Fatal Flaws in Deolalikar's Proof?|url=http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/|author={{Ill-wd|Q7326742|3=Dick Lipton}}|date=12 august 2010}}</ref>
În septembrie 2010, s-a afirmat că Deolalikar lucrează la o extindere detaliată a încercării sale de demonstrație.<ref>{{Citat web|url=http://rjlipton.wordpress.com/2010/09/15/an-update-on-vinay-deolalikars-proof/|titlu=An Update on Vinay Deolalikar's Proof|author={{Ill-wd|Q7326742|3=Dick Lipton}}|date=15 September 2010|accessdate=31 December 2010}}</ref> Opiniile exprimate de mai mulți informaticieni teoreticieni notabili indică însă că tentativa de demonstrație nu este nici corectă, nici nu reprezintă un progres semnificativ în înțelegerea problemei.<ref>Gödel’s Lost Letter and P=NP, [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/#comment-4885 Update on Deolalikar’s Proof that P≠NP]</ref> Această evaluare a făcut ca un articol publicat în mai 2013 în ''[[The New Yorker]]'' să spună că încercarea a fost „complet discreditată”.<ref>{{Citat web|url=http://www.newyorker.com/online/blogs/elements/2013/05/a-most-profound-math-problem.html|titlu=A Most Profound Math Problem|author=Alexander Nazaryan|date=2 May 2013|accessdate=1 May 2014}}</ref>

== Caracterizari logice ==
Problema '''P''' = '''NP''' poate fi reformulată în termenii anumitor clase de afirmații logice, ca un rezultat al activității din domeniul {{Ill-wd|Q1200755|3=complexității descriptive}}.

Să luăm în considerare toate limbajele cu structură finită cu o {{Ill-wd|Q741810|3=signatură}} fixă, inclusiv o relație de [[Relație de ordine totală|ordine totală]]. Atunci, toate aceste limbaje din '''P''' pot fi exprimate într-o {{Ill-wd|Q4055684|3=logică de ordinul întâi}}, cu adaosul unui{{Ill-wd|Q2976255|3= combinator de punct fix}} adecvat. Aceasta, în combinație cu relația de ordine, permite efectiv definirea de funcții recursive. Atâta timp cât signatura conține cel puțin un predicat sau o funcție în plus față de relația de ordine, astfel încât cantitatea de spațiu ocupată prin stocarea acestor structuri finite este de fapt polinomială în raport cu numărul de elemente în structură, aceasta caracterizează în mod precis '''P'''.

În mod similar, '''NP''' este un set de limbaje exprimabile într-o {{Ill-wd|Q1548746|3=logică de ordinul al doilea}} existențială—adică logică de ordinul al doilea restricționată prin excluderea [[Cuantificator universal|cuantificatorului universal]] peste relații, funcții, și submulțimi. Limbajele din {{Ill-wd|Q2103021|3=ierarhia polinomială}}, '''{{Ill-wd|Q1063380|3=PH-ul}}''', corespund întregii logici de ordinul al doilea. Astfel, la întrebarea „este '''P''' o submulțime proprie a lui '''NP'''” poate fi reformulată ca „este logica de ordinul al doilea existențială capabilă să descrie limbaje (cu structură finită și liniar ordonată cu signatură netrivială) pe care nu le poate descrie logica de ordinul întâi cu combinator de punct fix?".<ref>Elvira Mayordomo. </ref> Cuvântul „existențială” poate fi chiar eliminat din caracterizarea anterioară, deoarece '''P''' = '''NP''' [[dacă și numai dacă]] '''P''' = '''PH''' (întrucât prima ar stabili și că '''NP''' = '''co-NP''', care la rândul său implică faptul că '''NP''' = '''PH''').

== Algoritmi în timp polinomial ==
Nu se cunoaște niciun algoritm pentru vreo problemă '''NP'''-completă care să ruleze în timp polinomial. Există însă algoritmi pentru probleme '''NP'''-complete cu proprietatea că, dacă '''P''' = '''NP''', atunci algoritmul rulează în timp polinomial (deși cu constante enorme, ceea ce ar face algoritmul nepractic). Următorul algoritm, datorat lui {{Ill-wd|Q92966|3=Levin}} (fără citare), este un astfel de exemplu. El acceptă limbajul '''NP'''-complet SUBSET-SUM. Rulează în timp polinomial dacă și numai dacă '''P''' = '''NP''':
 // Algoritm care acceptă '''NP'''-complete limba SUBSET-SUM.
 //
 // acesta este un algoritm în timp polinomial dacă și numai dacă '''P''' = '''NP'''.
 //
 // "Timp polinomial" înseamnă că întoarce "da" în timp polinomial atunci când
 // raspunsul este "da", și ciclează la infinit atunci când este "nu".
 //
 // Intrare: S = o [[mulțime finită]] de numere întregi
 // Ieșire: "da" dacă orice submulțime a lui S are suma 0.
 // Ciclează la infinit fără ieșire în caz contrar.
 // Nota: "Programul nr. P" este programul obținut prin
 // scrierea întregului P în binar, apoi
 // considerând că șirul de biți obținut este un
 // program. Fiecare program posibil poate fi
 // generat în acest fel, deși cele mai multe nu fac nimic
 // din cauza erorilor de sintaxă. <br>
 
 PENTRU N = 1...∞
   PENTRU P = 1...N
     Rulează programul nr. P timp de N pași cu intrarea S
     DACĂ programul dă o listă de numere întregi distincte
        ȘI numerele sunt toate în S
        ȘI numerele au suma 0<br>
     ATUNCI
       Dă la IEȘIRE "da" și OPREȘTE-TE
Dacă, și numai dacă, '''P''' = '''NP''', atunci acesta este un algoritm în timp polinomial care acceptă orice limbaj '''NP'''-complet. „Acceptarea” înseamnă că dă răspunsuri „da” în timp polinomial, dar poate rula la nesfârșit atunci când răspunsul este „nu” (ceea ce se mai numește și ''semi-algoritm'').

Acest algoritm este extrem de nepractic, chiar și dacă '''P''' = '''NP'''. Dacă cel mai scurt program care poate rezolva SUBSET-SUM în timp polinomial are lungime de ''b'' biți, atunci algoritmul de mai sus va încerca cel puțin 2<sup>''b''</sup>-1 alte programe mai întâi.

== Definiții formale ==

=== P și NP ===
Conceptual vorbind, o ''problemă a deciziei'' este o problemă care are ca intrare un {{Ill-wd|Q184754|3=șir}} ''w'' peste un alfabet Σ, și ieșiri „da” sau „nu”. Dacă există un [[algoritm]] (să zicem o [[mașină Turing]], sau un [[Programare|program de calculator]] cu memorie nelimitată) care pot produce răspunsul corect pentru orice șir de intrare de lungime ''n'' , în cel mult ''cn<sup>k</sup>'' pași, în cazul în care ''k'' și ''c'' sunt constante independente de șirul de intrare, atunci putem spune că problema poate fi rezolvată în ''timp polinomial'' și o plasăm în clasa '''P'''. Formal, '''P''' este definită ca o mulțime a tuturor limbajelor care poate fi decise de o mașină Turing deterministă în timp polinomial. Adică,
: <math>\mathbf{P} = \{ L : L=L(M) \text{ pentru o mașină Turing deterministă în timp polinomial } M \}</math>
unde
: <math>L(M) = \{ w\in\Sigma^{*}: M \text{ acceptă } w \}</math>
și o mașină Turing deterministă în timp polinomial este o mașină Turing deterministă ''M'' care satisface următoarele două condiții:
# ''M'' se oprește pentru orice intrare ''w'' și
# există <math>k \in N</math> , astfel încât <math>T_M(n)\in O(n^k)</math>, unde ''O'' se referă la [[Notația Big O|notația big O]] și
:: <math>T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \}</math>
:: <math>t_M(w) = \text{ număr de pași de care are }M\text{ nevoie pentru a se opri la intrarea }w.</math>
'''NP''' poate fi definită în mod similar, folosind mașini Turing nedeterministe (în maniera tradițională). Cu toate acestea, o abordare modernă a definirii clasei '''NP''' este utilizarea conceptului de ''{{Ill-wd|Q2946816|3=certificat}}'' și ''verificator''. În mod oficial, '''NP''' este definit ca un set de limbaje peste un alfabet finit, care au un verificator care rulează în timp polinomial, unde noțiunea de „verificator” este definită după cum urmează.

Fie ''L'' un limbaj peste un alfabet finit, Σ.

''L'' ∈ '''NP''' dacă, și numai dacă, există o relație binară <math>R\subset\Sigma^{*}\times\Sigma^{*}</math> și un număr întreg pozitiv ''k'' astfel încât următoarele două condiții sunt îndeplinite:
# Oricare ar fi <math>x\in\Sigma^{*}</math>, <math>x\in L \Leftrightarrow\exists y\in\Sigma^{*}</math> astfel încât (''x'', ''y'') ∈ ''R'' și <math>|y|\in O(|x|^k)</math>; și
# limbajul <math>L_{R} = \{ x\# y:(x,y)\in R\}</math> peste <math>\Sigma\cup\{\#\}</math> este decidabil de către o mașină Turing, în timp polinomial.
O mașină Turing care decide ''L<sub>R</sub>'' se numește un ''verificator'' pentru ''L'' și un ''y'' astfel încât (''x'', ''y'') ∈ ''R'' se numește un ''certificat de apartenență'' al lui ''x'' în ''L''.

În general, un verificator nu trebuie să fie în timp polinomial. Cu toate acestea, pentru ca ''L'' să fie în '''NP''', trebuie să existe un verificator care rulează în timp polinomial.

==== Exemplu ====
Fie
: <math>\mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ pentru întregi } p, q > 1 \right \}</math>
: <math>R = \left \{(x,y)\in\mathbb{N} \times\mathbb{N} \mid 1<y \leq \sqrt x \text{ și } y \text{ divide } x \right \}.</math>
În mod clar, la întrebarea dacă un anumit ''x'' este [[Număr compus|compus]] este echivalentă cu întrebarea dacă ''x'' este un membru al COMPOSITE. Se poate demonstra că COMPOSITE ∈ '''NP''' , verificând că acesta îndeplinește definiția de mai sus (dacă vom identifica numerele naturale cu reprezentările lor binare).

COMPOSITE se întâmplă să fie și în '''P'''.<ref name="Agrawal">{{Citat web|author=M. Agrawal, N. Kayal, N. Saxena|titlu=Primes is in P|url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf|format=PDF|accessdate=29 December 2008}}</ref><ref>AKS primality test</ref>

=== NP-completitudinea ===
Există mai multe moduri echivalente de a descrie '''NP'''-completitudinea.

Fie ''L'' un limbaj peste un alfabet finit Σ.

''L'' este '''NP'''-complet dacă și numai dacă sunt îndeplinite următoarele două condiții:
# ''L'' ∈ '''NP'''; și
# orice ''L''' din '''NP''' este reductibil în timp polinomial la ''L'' (scris ca <math>L' \leq_{p} L</math>), unde <math>L' \leq_{p} L</math> , dacă și numai dacă sunt îndeplinite următoarele două condiții:
## Există ''f'' : Σ* → Σ* astfel încât pentru orice ''w'' din Σ*, avem: <math>(w\in L' \Leftrightarrow f(w)\in L)</math>; și
## există o mașină Turing în timp polinomial care se oprește cu ''f''(''w'') pe bandă la orice intrare ''w''.

== Cultura populară ==
* Filmul ''{{Ill-wd|Q7836080|3=Comis-voiajorul}}'', realizat de regizorul Timothy Lanzone, este povestea a patru matematicieni angajați de guvernul SUA pentru a rezolva problema P versus NP.<ref>{{Citat web|nume=Geere|last=Geere|first=Duncan|titlu='Travelling Salesman' movie considers the repercussions if P equals NP|url=http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman|publisher=Wired|accessdate=26 April 2012|archive-date=2016-05-14|archive-url=https://web.archive.org/web/20160514041511/http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman|dead-url=yes}}</ref>

== Note ==
{{listănote|group=lower-alpha}}

== Bibliografie ==
<references />

== Lectură suplimentară ==
* {{Citat revistă|doi=10.1007/3-540-10843-2_23|DOI=10.1007/3-540-10843-2_23|an=1981|titlu=Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N.|prenume=A. S.|nume=Fraenkel|prenume2=D.|nume2=Lichtenstein|journal=|volum=|număr=|pagini=|url=http://www.pubzone.org/dblp/conf/icalp/FraenkelL81|format=|access-date=|accessdate=|archive-date=2017-04-25|archive-url=https://web.archive.org/web/20170425031512/http://www.pubzone.org/dblp/conf/icalp/FraenkelL81|dead-url=yes}}
* {{Citat carte|nume=Garey|prenume=Michael|nume2=Johnson|prenume2=David|titlu=Computers and Intractability: A Guide to the Theory of NP-Completeness|editură={{Ill-wd|Q10392775}}|locul-publicării=San Francisco|an=1979|isbn=0-7167-1045-5}}
* {{Citat carte|nume=Goldreich|prenume=Oded|titlu=P, Np, and Np-Completeness|editură=Cambridge University Press|locul-publicării=Cambridge|an=2010|isbn=978-0-521-12254-2}} [http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html Online drafts]
* {{Citat revistă|nume=Immerman|prenume=N.|titlu=Languages which capture complexity classes|pagini=760–778|an=1987|journal=SIAM Journal of Computing|volum=16|număr=4|doi=10.1137/0216051|DOI=10.1137/0216051|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4936}}
* {{Citat carte|nume=Cormen|prenume=Thomas|titlu={{Ill-wd|Q1141518}}|editură=[[MIT Press]]|locul-publicării=Cambridge|an=2001|isbn=0-262-03293-7}}
* {{Citat carte|nume=Papadimitriou|prenume=Christos|titlu=Computational Complexity|editură=Addison-Wesley|locul-publicării=Boston|an=1994|isbn=0-201-53082-1}}
* {{Citat revistă|nume=Fortnow|prenume=L.|doi=10.1145/1562164.1562186|DOI=10.1145/1562164.1562186|titlu=The Status of the P versus NP problem|journal=Communications of the ACM|volum=52|număr=9|pagini=78|an=2009|url=http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext|pmid=|PMID=|pmc=|PMC=}}
* {{Citat web|last1=Fortnow|first1=L.|last2=Gasarch|first2=W.|titlu=Computational complexity|url=http://weblog.fortnow.com}}
* Fortnow, Lance. ''[http://press.princeton.edu/titles/9937.html The Golden Ticket: P, NP, and the Search for the Impossible]'' ISBN 9780691156491. [[Princeton University Press]]. Princeton, NJ (2013)

== Legături externe ==
* [http://www.claymath.org/millennium-problems Institutul de Matematică Clay: Problemele Premiului Mileniului]
* [http://www.claymath.org/sites/default/files/pvsnp.pdf Institutul de Matematică Clay: Descrierea oficială a problemei] {{Webarchive|url=https://web.archive.org/web/20150904090304/http://www.claymath.org/sites/default/files/pvsnp.pdf |date=2015-09-04 }} PDF (118 KB)
* {{Ill-wd|Q20994323}}. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Pagina P versus NP]. O listă de linkuri la o serie de pretinse soluții la această problemă. Unele dintre aceste linkuri afirmă că P este egal cu NP, alte afirmă contrariul. Foarte probabil, toate aceste presupuse soluții sunt incorecte.
* Blogul lui {{Ill-wd|Q4054157}} [http://scottaaronson.com/blog/?p=122 Shtetl Optimized: Motive pentru a crede], o listă a motivelor pentru credința că P ≠ NP

[[Categorie:Clase de complexitate]]
[[Categorie:Conjecturi]]
[[Categorie:Optimizare]]
[[Categorie:Probleme nerezolvate ale matematicii]]