Clasele de complexitate P și NP
From Wikipedia, the free encyclopedia
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.[2] 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”[3] și este considerată a fi cea mai importantă problemă deschisă din domeniu.[4] 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ă.
Dacă corectitudinea soluției unei probleme este ușor de verificat, este problema și ușor de rezolvat?
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.