miniatura|250x250px|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 .R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM, 22, pp. 151–171, 1975. 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 selectate de , 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ă 2n-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 (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 (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ă.Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. 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 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 dreapta|miniatura|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 este NP-completă conform , 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. Cum s-a arătat mai sus, aceasta este ; 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ă, a furnizat o manieră mai simplă de a arăta că multe alte probleme sunt NP-complete, inclusiv 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 . Pentru că se poate demonstra că P ≠ , aceste probleme sunt în afara P, și deci necesită timp mai mult decât polinomial. În fapt, prin , 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 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 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, cum ar fi 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.R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM, 22, pp. 151–171, 1975. Astfel de probleme se numesc probleme NP-intermediare. , 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ă, 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 și , a rulat timp de 2O(√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 (și chiar în UP și co-UPLance Fortnow. ). 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 , al cărui timp de rulare este
la factorizarea unui număr întreg pe n biți. Cu toate acestea, cel mai cunoscut pentru această problemă, , 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”?