Clasele de complexitate P și NP

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
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.[1]

Problema claselor de complexitate P și NP este o mare problemă nerezolvată din informatică⁠(d). Definind informal, ea este întrebarea dacă fiecare problemă a cărei soluții poate fi verificată 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ă⁠(d) poate fi rezolvată în timp pătratic⁠(d) sau liniar⁠(d).[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ă.

Termenul informal rapid, utilizat mai sus, se definește ca existența unui algoritm care rulează în timp polinomial⁠(d). 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 sproblema 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⁠(d)) 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[modificare | modificare sursă]

Relația între clasele de complexitate P și NP este studiată în teoria complexității computaționale, ramura teoriei computației⁠(d) 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⁠(d) date fiind informațiile corecte, sau echivalent, a cărei soluție poate fi găsită în timp polinomial pe o mașină nedeterministă⁠(d).[5] Evident, PNP. 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.[6]

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

NP-completitudinea[modificare | modificare sursă]

Diagramă Euler⁠(d) 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 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-grele 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?[8] 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[modificare | modificare sursă]

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ă PEXPTIME⁠(d), aceste probleme sunt în afara P, și deci necesită timp mai mult decât polinomial. În fapt, prin timp ierarhie teorema⁠(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)[9] și alte jocuri de masă.[10]

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 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[modificare | modificare sursă]

S-a demonstrat de către Ladner că dacă PNP atunci există probleme în NP care nu sunt nici în P nici NP-complete.[1] Astfel de probleme se numesc probleme NP-intermediare. Problema izomorfismului grafurilor⁠(d), problema logaritmului discret⁠(d) și problema factorizării numerelor întregi problemă 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⁠(d). 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ă.[11] Dacă izomorfismul grafurilor ar fi NP-completă, ierarhia timpului polinomial⁠(d) s-ar plia la al doilea nivel.[12][13] 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 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 Co-NP⁠(d) (și chiar în UP și co-UP[14]). 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

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”?[modificare | modificare sursă]

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 stat-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))2).[15]

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ă PNP, încă ar putea exista abordări eficiente pentru rezolvarea problemei pe cazurile practice. Există algoritmi pentru multe NP-complete, cum ar fi problema rucsacului⁠(d), problema comis-voiajorului⁠(d) ș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.[16]

Î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[modificare | modificare sursă]

Potrivit sondajelor,[6][17] mulți informaticieni cred că PNP. 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⁠(d), 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ă.[18]

Pe de altă parte, unii cercetători cred că încrederea că PNP 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:[6]

Consecințele unei soluții[modificare | modificare sursă]

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[modificare | modificare sursă]

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

  • criptografia cu chei publice,[19] 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,[20] 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[21] 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.[22]

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⁠(d). 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;[23] 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 pe complexitatea computațională, Gödel a menționat că o metodă mecanică care ar putea rezolva orice problemă ar revoluționa matematica:[24][25]

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

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

P ≠ NP[modificare | modificare sursă]

O demonstrație că PNP 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ă PNP, o mare parte din această schimbare a avut deja loc.[28]

De asemenea, PNP lasă încă deschisă chestiunea complexitatăț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.[29] 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 PNP ș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 PNP 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.[30]

Rezultate despre dificultatea demonstrației[modificare | modificare sursă]

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ă PNP:

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 PNP în raport cu alte oracole.[31] Î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⁠(d) 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.[32]

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 teoria mulțimilor Zermelo–Fraenkel⁠(d) (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.[33] 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.[34] 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[modificare | modificare sursă]

În timp ce problema P versus NP este în general considerată nerezolvată,[35] mulți amatori și unii cercetători profesioniști au susținut soluții. Gerhard J. Woeginger⁠(d) are o listă cuprinzătoare.[36] O demonstrație propusă în august 2010 că PNP, 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.[37] Demonstrația a fost revizuit în mod public de către mediul academic,[38][39] și Neil Immerman⁠(d), un expert în domeniu, a subliniat două erori posibil fatale ale demonstrației.[40] În septembrie 2010, s-a afirmat că Deolalikar lucrează la o extindere detaliată a încercării sale de demonstrație.[41] 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.[42] Această evaluare a făcut ca un articol publicat în mai 2013 în The New Yorker să spună că încercarea a fost „complet discreditată”.[43]

Caracterizari logice[modificare | modificare sursă]

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 strictură 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⁠(d) 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?".[44] 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[modificare | modificare sursă]

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 2b-1 alte programe mai întâi.

Definiții formale[modificare | modificare sursă]

P și NP[modificare | modificare sursă]

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 cnk 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ă,

unde

ș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ă , astfel încât , unde O se referă la notația big O⁠(d) și

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, Σ.

LNP dacă, și numai dacă, există o relație binară  și un număr întreg pozitiv k astfel încât următoarele două condiții sunt îndeplinite:

  1. Oricare ar fi , astfel încât (x, y) ∈ R și ; și
  2. limbajul  peste este decidabil de către o mașină Turing, în timp polinomial.

O mașină Turing care decide LR 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[modificare | modificare sursă]

Fie

Î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.[45][46]

NP-completitudinea[modificare | modificare sursă]

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. LNP; și
  2. orice L' din NP este reductibil în timp polinomial la L (scris ca ), unde  , dacă și numai dacă sunt îndeplinite următoarele două condiții:
    1. Există f : Σ* → Σ* astfel încât pentru orice w din Σ*, avem: ; ș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ă[modificare | modificare sursă]

  • 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.[47]

Note[modificare | modificare sursă]

  1. ^ 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 sau mai bună și cu un termen constant rezonabil ar fi dezastruoasă. Pe de altă parte, o soluție care este sau mai rea în aproape toate cazurile nu ar pune niciun pericol practic imediat.

Bibliografie[modificare | modificare sursă]

  1. ^ a b R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM, 22, pp. 151–171, 1975.
  2. ^ Hartmanis, Juris. „Gödel, von Neumann, and the P = NP problem” (PDF). Bulletin of the European Association for Theoretical Computer Science 38: 101–107. http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf. 
  3. ^ Cook, Stephen (1971). „The complexity of theorem proving procedures”. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047 
  4. ^ Fortnow, Lance (2009). „The status of the P versus NP problem” (PDF). Communications of the ACM 52 (9): 78–86. doi:10.1145/1562164.1562186. http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf. 
  5. ^ Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270.
  6. ^ a b c William I. Gasarch (1 iunie 2002). „The P=?NP poll.” (PDF). SIGACT News 33 (2): 34–47. doi:10.1145/1052796.1052804. http://www.cs.umd.edu/~gasarch/papers/poll.pdf. Accesat la 29 decembrie 2008. 
  7. ^ William I. Gasarch. „The Second P=?NP poll” (PDF). SIGACT News 74. http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf. 
  8. ^ Scott Aaronson. „PHYS771 Lecture 6: P, NP, and Friends. http://www.scottaaronson.com/democritus/lec6.html. Accesat la 27 august 2007. 
  9. ^ Aviezri Fraenkel⁠(d) and D. Lichtenstein (1981). „Computing a perfect strategy for n×n chess requires time exponential in n”. J. Comb. Th. A (31): 199–214. 
  10. ^ David Eppstein⁠(d). „Computational Complexity of Games and Puzzles. http://www.ics.uci.edu/~eppstein/cgt/hard.html. 
  11. ^ Arvind, Vikraman; Kurur, Piyush P. (2006). „Graph isomorphism is in SPP”. Information and Computation 204 (5): 835–852. doi:10.1016/j.ic.2006.02.002. 
  12. ^ Schöning, Uwe. „Graph isomorphism is in the low hierarchy”. Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science⁠(d) 1987: 114–124. doi:10.1007/bfb0039599. 
  13. ^ Schöning, Uwe (1988). „Graph isomorphism is in the low hierarchy”. Journal of Computer and System Sciences 37: 312–323. doi:10.1016/0022-0000(88)90010-4. 
  14. ^ Lance Fortnow.
  15. ^ Pisinger, D. 2003.
  16. ^ Gondzio, Jacek; Terlaky, Tamás (1996). „3 A computational view of interior point methods”. în J. E. Beasley. Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. 4. New York: Oxford University Press. pp. 103–144. Postscript file at website of Gondzio and at McMaster University website of Terlaky. http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps 
  17. ^ Rosenberger, Jack (1 mai 2012). „P vs. NP poll results”. Communications of the ACM 55 (5): 10. http://mags.acm.org/communications/201205?pg=12. 
  18. ^ Scott Aaronson. „Reasons to believe. http://scottaaronson.com/blog/?p=122. 
  19. ^ See Horie, S. and Watanabe, O.; Watanabe (1997). „Hard instance generation for SAT”. Algorithms and Computation. Lecture Notes in Computer Science (Springer) 1350: 22–31. doi:10.1007/3-540-63890-3_4. ISBN 978-3-540-63890-2. Bibcode1998cs........9117H. 
  20. ^ See, for example, Massacci, F. and Marraro, L. (2000). „Logical cryptanalysis as a SAT problem”. Journal of Automated Reasoning (Springer) 24 (1): 165–203. doi:10.1023/A:1006326723002. Format:Citeseerx. 
  21. ^ Find a messageM that when hashed by the function H() gives a digest h, or H(M)=h
  22. ^ De, Debapratim and Kumarasubramanian, Abishek and Venkatesan, Ramarathnam. „Inversion attacks on secure hash functions using SAT solvers”. Springer. pp. 377–382. 
  23. ^ Berger B⁠(d), Leighton T⁠(d) (1998). „Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete”. J. Comput. Biol. 5 (1): 27–40. doi:10.1089/cmb.1998.5.27. PMID 9541869. 
  24. ^ History of this letter and its translation from Michael Sipser. „The History and Status of the P versus NP question. http://cs.stanford.edu/people/trevisan/cs172-07/sipser92history.pdf. 
  25. ^ David S. Johnson. „A Brief History of NP-Completeness, 1954–2012. http://www.research.att.com/techdocs/TD_100899.pdf. 
  26. ^ Cook, Stephen (1 aprilie 2000). The P versus NP Problem. Clay Mathematics Institute⁠(d). http://www.claymath.org/sites/default/files/pvsnp.pdf. Accesat la 18 octombrie 2006. 
  27. ^ Knuth, Donald E. (20 mai 2014). „Twenty Questions for Donald Knuth”. informit.com. InformIT⁠(en). 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. Accesat la 20 iulie 2014. 
  28. ^ L. R. Foulds (1 octombrie 1983). „The Heuristic Problem-Solving Approach”. Journal of the Operational Research Society⁠(d) 34 (10): 927–934. doi:10.2307/2580891. 
  29. ^ R. Impagliazzo, "A personal view of average-case complexity," sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995
  30. ^ Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds"”. Există o versiune arhivată la 15 noiembrie 2013. https://web.archive.org/web/20131115034042/http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds/. 
  31. ^ T. P. Baker, J. Gill, R. Solovay.
  32. ^ S. Aaronson and A. Wigderson (2008).
  33. ^ Aaronson, Scott. „Is P Versus NP Formally Independent?. http://www.scottaaronson.com/papers/pnp.pdfFormat:Inconsistent citations 
  34. ^ Ben-David, Shai; Halevi, Shai (1992). On the independence of P versus NP. Technical Report. 714. Technion. http://www.cs.technion.ac.il/~shai/ph.ps.gzFormat:Inconsistent citations 
  35. ^ John Markoff⁠(d) (8 octombrie 2009). „Prizes Aside, the P-NP Puzzler Has Consequences”. The New York Times. http://www.nytimes.com/2009/10/08/science/Wpolynom.html. 
  36. ^ Gerhard J. Woeginger. „The P-versus-NP page. http://www.win.tue.nl/~gwoegi/P-versus-NP.htm. Accesat la 25 mai 2014. 
  37. ^ Markoff, John (16 august 2010). „Step 1: Post Elusive Proof. Step 2: Watch Fireworks.”. The New York Times. http://www.nytimes.com/2010/08/17/science/17proof.html?_r=1. Accesat la 20 septembrie 2010. 
  38. ^ Polymath project⁠(d) wiki. „Deolalikar's P vs NP paper. http://michaelnielsen.org/polymath1/index.php?title=Deolalikar_P_vs_NP_paper. 
  39. ^ Science News, "Crowdsourcing peer review"
  40. ^ Dick Lipton⁠(d) (12 august 2010). „Fatal Flaws in Deolalikar's Proof?. http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/. 
  41. ^ Dick Lipton⁠(d) (15 septembrie 2010). „An Update on Vinay Deolalikar's Proof. http://rjlipton.wordpress.com/2010/09/15/an-update-on-vinay-deolalikars-proof/. Accesat la 31 decembrie 2010. 
  42. ^ Gödel’s Lost Letter and P=NP, Update on Deolalikar’s Proof that P≠NP
  43. ^ Alexander Nazaryan (2 mai 2013). „A Most Profound Math Problem. http://www.newyorker.com/online/blogs/elements/2013/05/a-most-profound-math-problem.html. Accesat la 1 mai 2014. 
  44. ^ Elvira Mayordomo.
  45. ^ M. Agrawal, N. Kayal, N. Saxena. „Primes is in P” (PDF). http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf. Accesat la 29 decembrie 2008. 
  46. ^ AKS primality test
  47. ^ Geere, Duncan. „'Travelling Salesman' movie considers the repercussions if P equals NP”. Wired. http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman. Accesat la 26 aprilie 2012. 

Lectură suplimentară[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]