Clasele de complexitate P și NP

Problemă nerezolvată în informatică:

Dacă corectitudinea soluției unei probleme este ușor de verificat, este problema și ușor de rezolvat?

(mai multe probleme nerezolvate din informatică)

Problema claselor de complexitate P și NP este o mare 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-completă poate fi rezolvată în timp pătratic sau liniar. 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” și este considerată a fi cea mai importantă problemă deschisă din domeniu. Este una dintre cele șapte probleme pentru Premiul Mileniului^⁠(d) selectate de Clay Mathematics Institute^⁠(d), care oferă un premiu de 1.000.000 de dolari pentru prima soluție corectă.

Diagramă a claselor de complexitate, cu premisa că P ≠ NP. În această ipoteză, existența problemelor din NP, dar care nu sunt nici P și nici NP-complete, a fost stabilită prin teorema lui Ladner^⁠(d).

Termenul informal rapid, utilizat mai sus, se definește ca existența unui algoritm care rulează în 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”. 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, 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 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  {−2, −3, 15, 14, 7, −10} ale cărei elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea  {−2, −3, −10, 15} 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ⁿ-n-1 încercări). Un astfel de algoritm există doar dacă P = NP; deci această problemă este în NP (rapid verificabilă) dar nu neapărat în P (rapid rezolvabilă).

Soluția problemei P = 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 ≠ NP, ar însemna că există probleme din NP (cum ar fi problemele 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, filosofie, economie și în multe alte domenii.

Context

Relația între clasele de complexitate P și NP este studiată în teoria complexității computaționale, ramura 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 determinist^⁠(d) (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 probleme ale deciziei^⁠(d) (definite mai jos) care pot fi rezolvate pe o mașină deterministă secvențială într-un timp polinomial în funcție de dimensiunea intrării; clasa NP constă din acele probleme de decizie ale căror soluții pozitive pot fi verificate în 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ă nedeterministă. 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 independentă^⁠(d) de axiomele actual acceptate și astfel imposibil de demonstrat într-un sens sau altul.

Î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.

NP-completitudinea

Diagramă Euler pentru seturile de probleme P, 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, problema satisfiabilității booleene^⁠(d) este NP-completă conform teoremei Cook–Levin^⁠(d), 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? 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 problema satisfiabilității booleene^⁠(d). Cum s-a arătat mai sus, aceasta este teorema Cook–Levin^⁠(d); 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ă, demonstrația prin reducere^⁠(d) a furnizat o manieră mai simplă de a arăta că multe alte probleme sunt NP-complete, inclusiv problema sumei elementelor submulțimilor^⁠(d) 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 EXPTIME-complete^⁠(d). Pentru că se poate demonstra că P ≠ EXPTIME^⁠(d), aceste probleme sunt în afara P, și deci necesită timp mai mult decât polinomial. În fapt, prin teorema ierarhiei temporale^⁠(d), 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) și alte jocuri de masă.

Problema de a decide adevărul unei afirmații în aritmetica Presburger^⁠(d) necesită și mai mult timp. Fischer și 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 $2^{2^{cn}}$ 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 problemele indecidabile^⁠(d), cum ar fi problema opririi^⁠(d). 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. Astfel de probleme se numesc probleme NP-intermediare. Problema izomorfismului grafurilor^⁠(d), problema logaritmului discret și 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ă grafuri finite sunt 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ă. Dacă izomorfismul grafurilor ar fi NP-completă, ierarhia timpului polinomial^⁠(d) s-ar plia la al doilea nivel. 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 László Babai^⁠(d) și Eugene M. Luks^⁠(d), a rulat timp de 2^{O(√nlog(n))} pentru un graf cu n noduri.

Problema factorizării numerelor întregi este problema calculului 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 co-NP^⁠(d) (și chiar în UP și co-UP). 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 ciurul câmpurilor de numere generalizat^⁠(d), al cărui timp de rulare este

$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)$

la factorizarea unui număr întreg pe n biți. Cu toate acestea, cel mai cunoscut algoritm cuantic^⁠(d) pentru această problemă, algoritmul lui Shor^⁠(d), 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”?

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 state-of-the-art. Curba de regresie pătratică sugerează că complexitatea algoritmică empirică pentru cazuri cu 50–10.000 de variabile este O((log(n))²).

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 teza lui Cobham^⁠(d). 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 comis-voiajorului și problema satisfiabilității booleene^⁠(d), care pot rezolva optim multe cazuri din lumea reală asociate lor într-un timp rezonabil. Complexitatea cazului mediu^⁠(d) (timp vs dimensiunea problemei) a acestui fel de algoritmi poate fi surprinzător de scăzută. Un exemplu este algoritmul simplex din 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.

Î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 calculul cuantic și algoritmii probabilistici^⁠(d).

Motive pentru a crede că P ≠ NP

Potrivit sondajelor, 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 Lista de probleme NP-complete^⁠(d)). 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, 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 = co-NP^⁠(d) și P = PH^⁠(d).

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ă.

„Dacă P = 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.”

— Scott Aaronson^⁠(d), 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:

„Principalul argument în favoarea ideii că P ≠ 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 Ultimei Teoreme a lui Fermat arată și că întrebările foarte simple pot primi un răspuns doar din partea unor teorii foarte profunde.”

—Moshe Vardi^⁠(d), Rice University^⁠(d)

„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.”

—Anil Nerode^⁠(d), 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 neconstructivă^⁠(d), 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ă pentru o problemă NP-completă, cum ar fi 3-SAT^⁠(d),  ar distruge majoritatea criptosistemelor existente, între care:

• criptografia cu chei publice, un fundament pentru multe aplicații de securitate, cum ar fi tranzacțiile financiare prin Internet; și
• cifrurile simetrice^⁠(d) , cum ar fi AES sau 3DES, folosite pentru criptarea datelor în comunicații.
• funcțiile unidirecționale^⁠(d) utilizate în hash-urile criptografice. Problema găsirii unei pre-imagini al cărui hash este anumită valoare 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.

Acestea ar trebui să fie modificate sau înlocuite cu soluții informatic sigure^⁠(d) 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 cercetarea operațională^⁠(d) sunt NP-complete, cum ar fi unele tipuri de probleme cu numere întregi^⁠(d) și 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 predicția structurilor proteinelor^⁠(d), sunt, de asemenea, NP-complete; 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:

„Dacă chiar ar exista o mașină cu φ(n) ∼ k ⋅ n (sau chiar ∼ k ⋅ n²), aceasta ar avea consecințe de cea mai mare importanță. Și anume, ar însemna evident că în ciuda indecidabilității 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

„...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, 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 Knuth a declarat că el a ajuns să creadă că P = NP, dar este rezervat cu privire la impactul unei posibile dovezi:

„[...] 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.

De asemenea, P ≠ NP lasă încă deschisă chestiunea complexității pe cazul mediu^⁠(d) 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. Russell Impagliazzo^⁠(d) a descris cinci „lumi” ipotetice, care ar putea duce la diferite rezoluții posibile pentru chestiunea complexității cazului mediu. 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.

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:

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ă oracol⁠(d), ș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 Solovay⁠(d) au arătat că P = NP în raport cu unele oracole, în timp ce P ≠ NP în raport cu alte oracole. Î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.
Demonstrații naturale⁠(d)	În 1993, Alexander Razborov⁠(d) și Steven Rudich⁠(d) au definit o clasă generală de tehnici de demonstrație pentru limita inferioară a complexității circuitelor, denumite demonstrații naturale⁠(d). 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ă funcții unidirecționale⁠(d), 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ă IP⁠(d) = PSPACE⁠(d). Cu toate acestea, în 2008, Scott Aaronson⁠(d) ș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.

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 independentă^⁠(d) 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. 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 axiomele Peano^⁠(d) (PA) pentru aritmetica numerelor întregi, atunci ar exista în mod necesar algoritmi în timp cvasipolinomial pentru orice problemă din NP. 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ă, mulți amatori și unii cercetători profesioniști au susținut soluții. Gerhard Woeginger^⁠(d) are o listă cuprinzătoare. O demonstrație propusă în august 2010 că P ≠ NP, de Vinay Deolalikar, cercetător de la HP Labs^⁠(d), 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. Demonstrația a fost revizuit în mod public de către mediul academic, și Neil Immerman^⁠(d), un expert în domeniu, a subliniat două erori posibil fatale ale demonstrației. În septembrie 2010, s-a afirmat că Deolalikar lucrează la o extindere detaliată a încercării sale de demonstrație. 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. Această evaluare a făcut ca un articol publicat în mai 2013 în The New Yorker să spună că încercarea a fost „complet discreditată”.

Caracterizari logice

Problema P = NP poate fi reformulată în termenii anumitor clase de afirmații logice, ca un rezultat al activității din domeniul complexității descriptive^⁠(d).

Să luăm în considerare toate limbajele cu structură finită cu o signatură^⁠(d) fixă, inclusiv o relație de ordine totală. Atunci, toate aceste limbaje din P pot fi exprimate într-o logică de ordinul întâi^⁠(d), cu adaosul unui combinator de punct fix^⁠(d) 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 logică de ordinul al doilea^⁠(d) existențială—adică logică de ordinul al doilea restricționată prin excluderea cuantificatorului universal peste relații, funcții, și submulțimi. Limbajele din ierarhia polinomială^⁠(d), PH-ul^⁠(d), 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?". 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 Levin^⁠(d) (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ă. 


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

    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^b-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 șir^⁠(d) w peste un alfabet Σ, și ieșiri „da” sau „nu”. Dacă există un algoritm (să zicem o mașină Turing, sau un program de calculator cu memorie nelimitată) care pot produce răspunsul corect pentru orice șir de intrare de lungime n , în cel mult cn^k 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ă,

$\mathbf {P} =\{L:L=L(M){\text{ pentru o mașină Turing deterministă în timp polinomial }}M\}$

unde

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

și o mașină Turing deterministă în timp polinomial este o mașină Turing deterministă M care satisface următoarele două condiții:

1. M se oprește pentru orice intrare w și
2. există $k\in N$ , astfel încât $T_{M}(n)\in O(n^{k})$, unde O se referă la notația big O și

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

$t_{M}(w)={\text{ număr de pași de care are }}M{\text{ nevoie pentru a se opri la intrarea }}w.$

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 certificat^⁠(d) ș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ă $R\subset \Sigma ^{*}\times \Sigma ^{*}$ și un număr întreg pozitiv k astfel încât următoarele două condiții sunt îndeplinite:

1. Oricare ar fi $x\in \Sigma ^{*}$, $x\in L\Leftrightarrow \exists y\in \Sigma ^{*}$ astfel încât (x, y) ∈ R și $|y|\in O(|x|^{k})$; și
2. limbajul $L_{R}=\{x\#y:(x,y)\in R\}$ peste $\Sigma \cup \{\#\}$ este decidabil de către o mașină Turing, în timp polinomial.

O mașină Turing care decide L_R 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

$\mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ pentru întregi }}p,q>1\right\}$

$R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ și }}y{\text{ divide }}x\right\}.$

În mod clar, la întrebarea dacă un anumit x este 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.

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:

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

Cultura populară

• Filmul Comis-voiajorul^⁠(d), realizat de regizorul Timothy Lanzone, este povestea a patru matematicieni angajați de guvernul SUA pentru a rezolva problema P versus NP.

Lectură suplimentară

• Fraenkel, A. S.; Lichtenstein, D. (1981). „Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N”. doi:10.1007/3-540-10843-2_23. Arhivat din original la 25 aprilie 2017. 
• Garey, Michael; Johnson, David (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company^⁠(d). ISBN 0-7167-1045-5. 
• Goldreich, Oded (2010). P, Np, and Np-Completeness. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2.  Online drafts
• Immerman, N. (1987). „Languages which capture complexity classes”. SIAM Journal of Computing. 16 (4): 760–778. doi:10.1137/0216051. 
• Cormen, Thomas (2001). Introduction to Algorithms^⁠(d). Cambridge: MIT Press. ISBN 0-262-03293-7. 
• Papadimitriou, Christos (1994). Computational Complexity. Boston: Addison-Wesley. ISBN 0-201-53082-1. 
• Fortnow, L. (2009). „The Status of the P versus NP problem”. Communications of the ACM. 52 (9): 78. doi:10.1145/1562164.1562186. 
• Fortnow, L.; Gasarch, W. „Computational complexity”. 
• Fortnow, Lance. The Golden Ticket: P, NP, and the Search for the Impossible ISBN 9780691156491. Princeton University Press. Princeton, NJ (2013)

Legături externe

• Institutul de Matematică Clay: Problemele Premiului Mileniului
• Institutul de Matematică Clay: Descrierea oficială a problemei Arhivat în 4 septembrie 2015, la Wayback Machine. PDF (118 KB)
• Gerhard Woeginger^⁠(d). 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 Scott Aaronson^⁠(d) Shtetl Optimized: Motive pentru a crede, o listă a motivelor pentru credința că P ≠ NP