Clasele de complexitate P și NP

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 Format:Ill-wd.

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 Format:Ill-wd selectate de Format:Ill-wd, 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 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 Format:Ill-wd (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 Format:Ill-wd (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 Format:Ill-wd 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, Format:Ill-wd este NP-completă conform Format:Ill-wd, 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 Format:Ill-wd. Cum s-a arătat mai sus, aceasta este Format:Ill-wd; 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ă, Format:Ill-wd a furnizat o manieră mai simplă de a arăta că multe alte probleme sunt NP-complete, inclusiv Format:Ill-wd 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 Format:Ill-wd. Pentru că se poate demonstra că P ≠ Format:Ill-wd, aceste probleme sunt în afara P, și deci necesită timp mai mult decât polinomial. În fapt, prin Format:Ill-wd, 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 Format:Ill-wd 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 suntFormat:Ill-wd, cum ar fi Format:Ill-wd. 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. Format:Ill-wd, 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ă, Format:Ill-wd 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 Format:Ill-wd și Format:Ill-wd, 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 Format:Ill-wd (ș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 Format:Ill-wd, al cărui timp de rulare este

$O(\exp \left({(\frac{64n}{9}\log (2))}^{\frac{1}{3}}{(\log (n\log (2)))}^{\frac{2}{3}}\right))$

la factorizarea unui număr întreg pe n biți. Cu toate acestea, cel mai cunoscut Format:Ill-wd pentru această problemă, Format:Ill-wd, 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 Format:Lang. 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 Format:Ill-wd. 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 Format:Ill-wd, care pot rezolva optim multe cazuri din lumea reală asociate lor într-un timp rezonabil. Format:Ill-wd (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 Format:Ill-wd.

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 Format:Ill-wd). 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 = Format:Ill-wd și P = Format:Ill-wd.

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ă. Format:Quote

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: Format:Quote Format:Quote

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 Format:Ill-wd, 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 Format:Ill-wd,  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
• Format:Ill-wd , cum ar fi AES sau 3DES, folosite pentru criptarea datelor în comunicații.
• Format:Ill-wd 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 Format:Ill-wd 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 Format:Ill-wd sunt NP-complete, cum ar fi unele tipuri de Format:Ill-wd ș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 Format:Ill-wd, 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:

În mod similar, Stephen Cook spune Format:Quote

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: Format:Quote

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 Format:Ill-wd 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. Format:Ill-wd 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ă Format:Ill-wd, ș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 Format:Ill-wd 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.
Format:Ill-wd	În 1993, Format:Ill-wd și Format:Ill-wd au definit o clasă generală de tehnici de demonstrație pentru limita inferioară a complexității circuitelor, denumite Format:Ill-wd. 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ă Format:Ill-wd, 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ă Format:Ill-wd = Format:Ill-wd. Cu toate acestea, în 2008, Format:Ill-wd ș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 Format:Ill-wd 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 Format:Ill-wd (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. Format:Ill-wd are o listă cuprinzătoare. O demonstrație propusă în august 2010 că P ≠ NP, de Vinay Deolalikar, cercetător de la Format:Ill-wd, 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 Format:Ill-wd, 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 Format:Ill-wd.

Să luăm în considerare toate limbajele cu structură finită cu o Format:Ill-wd fixă, inclusiv o relație de ordine totală. Atunci, toate aceste limbaje din P pot fi exprimate într-o Format:Ill-wd, cu adaosul unuiFormat:Ill-wd 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 Format:Ill-wd existențială—adică logică de ordinul al doilea restricționată prin excluderea cuantificatorului universal peste relații, funcții, și submulțimi. Limbajele din Format:Ill-wd, Format:Ill-wd, 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 Format:Ill-wd (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 Format:Ill-wd 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ă,

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

unde

$L(M)=\{w\in {\mathrm{\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 {\mathrm{\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 Format:Ill-wd ș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 {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$ și un număr întreg pozitiv k astfel încât următoarele două condiții sunt îndeplinite:

1. Oricare ar fi $x\in {\mathrm{\Sigma }}^{*}$, $x\in L\iff \mathrm{\exists }y\in {\mathrm{\Sigma }}^{*}$ astfel încât (x, y) ∈ R și $|y|\in O(|x{|}^k)$; și
2. limbajul $L_R=\{x\mathrm{\#}y:(x,y)\in R\}$ peste $\mathrm{\Sigma }\cup \{\mathrm{\#}\}$ 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{C}\mathrm{O}\mathrm{M}\mathrm{P}\mathrm{O}\mathrm{S}\mathrm{I}\mathrm{T}\mathrm{E}=\{x\in \mathbb{N}\mid x=pq\text{ pentru întregi }p,q>1\}$

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

Î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^{\prime }{\le }_{p}L$), unde $L^{\prime }{\le }_{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^{\prime }\iff 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 Format:Ill-wd, realizat de regizorul Timothy Lanzone, este povestea a patru matematicieni angajați de guvernul SUA pentru a rezolva problema P versus NP.

Lectură suplimentară

• Format:Citat revistă
• Format:Citat carte
• Format:Citat carte Online drafts
• Format:Citat revistă
• Format:Citat carte
• Format:Citat carte
• Format:Citat revistă
• Format:Citat web
• 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 Format:Webarchive PDF (118 KB)
• Format:Ill-wd. 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 Format:Ill-wd Shtetl Optimized: Motive pentru a crede, o listă a motivelor pentru credința că P ≠ NP