P=NP?În episodul de Halloween din 1995 de la The Simpsons, Homer Simpson găseşte un portal către o misterioasă A Treia Dimensiune în spatele unui raft de cărţi şi, disperat să scape de rudele sale prin alianţă, se aruncă prin respectivul portal.

 

 

Se trezeşte rătăcind pe o suprafaţă întunecată gravată cu o reţea de linii verzi şi presărată cu forme geometrice, deasupra plutind ecuaţii ciudate. Una dintre acestea este afirmaţia înşelătoare prin simplitatea ei că P = NP.


Cea mai notorie problemă din informatica teoretică rămâne deschisă, dar încercările de a o rezolva au dus la intuiţii profunde.

 

De fapt, într-un sondaj de opinie din 2002, 61 de matematicieni şi informaticieni au spus că ei au crezut că probabil P nu este egal cu NP , faţă de doar nouă care au fost de acord cu afirmaţia – şi dintre aceşti nouă mai mulţi au declarat în sondaje că au adoptat această poziţie doar pentru a fi contra. Dar până acum nimeni nu a fost capabil să răspundă decisiv la întrebare, într-un fel sau altul. Numită frecvent întrebarea cu importanţa cea mai mare în informatica teoretică, echivalenţa lui P cu NP este una din cele şapte probleme pentru care Clay Mathematics Institute vă va oferi un milion de dolari pentru a o demonstra - sau nega. Aproximativ vorbind, P este un set de probleme relativ uşoare, iar NP este un set de ceea ce par a fi probleme foarte, foarte grele, astfel încât P = NP ar însemna că problemele aparent dificile, de fapt, au soluţii relativ uşoare. Dar detaliile sunt mult mai complicate.

Informatica este în cea mai mare parte îngrijorată de o singură întrebare: De cât timp este nevoie pentru a executa un algoritm dat? Dar informaticienii nu dau răspunsul în câteva minute sau milisecunde, aceştia dau răspunsul comparativ cu numărul de elemente pe care algoritmul le are de manipulat.

Imaginaţi-vă, de exemplu, că aveţi o listă de numere nesortate şi doriţi să scrieţi un algoritm pentru a-l găsi pe cel mai mare. Algoritmul trebuie să ia în considerare toate numerele din listă: nu există altă variantă. Dar dacă păstrează pur şi simplu o înregistrare cu cel mai mare număr pe care l-a văzut în fiecare moment, se va uita la fiecare intrare doar o singură dată. Timpul necesar execuţiei unui algoritm este, astfel, direct proporţional cu numărul de elemente de manipulat - pe care informaticienii l-au numit N. Desigur, cei mai mulţi algoritmi sunt mult mai complicaţi şi, astfel, mai puţin eficienţi, decât unul care găseşte cel mai mare număr dintr-o listă, dar cei mai familiari algoritmi au timpul de execuţie proporţional cu N2, sau de N ori logaritm (N) sau altceva asemănător.

O expresie matematică care implică ridicarea la diferite puteri a lui N (N, N2 şi alte puteri) se numeşte un polinom şi asta este ceea la ce "P" din "P = NP" se referă. P este un set de probleme al căror timp de rezolvare este proporţional cu expresii polinomiale ale lui N.

Evident, un algoritm al cărui timp de execuţie este proporţional cu N3 este mai lent decât cel al cărui timp de execuţie este proporţional cu N. Dar astfel de diferenţe sunt nesemnificative în comparaţie cu o altă diferenţă, între expresiile polinomiale - unde N este numărul care va fi ridicat la o putere - şi expresiile exponenţiale, unde un număr este ridicat la puterea N, precum, să spunem, 2N.

Dacă unui algoritm al cărui timp de execuţie este proporţional cu N îi ia o secundă pentru a efectua un calcul care implică 100 de elemente, unui algoritm al cărui timp de execuţie este proporţional cu N3 îi va lua aproape trei ore. Dar unui algoritm cu un timp de execuţie proporţional cu 2N îi va lua 300 de cvintilioane (1030) de ani. Această discrepanţă devine din ce în ce mai deranjantă odată cu creşterea lui N.

NP (care înseamnă timp polinomial nedeterminat) este setul de probleme ale căror soluţii pot fi verificate în timp polinomial. Dar, conform celor ştiute în prezent, multe dintre aceste probleme necesită timp exponențial pentru rezolvare. Poate că problema cea mai cunoscută din NP, de exemplu, este de a găsi factorii primi ai unui număr mare. Verificarea unei soluţii necesită doar multiplicare, dar rezolvarea problemei pare a cere în mod sistematic  încercarea unei mulţimi de candidaţi.

 

 

Deci, întrebarea "este NP egal cu P?" înseamnă "dacă soluţia unei probleme poate fi verificată în timp polinomial, poate fi şi găsită în timp polinomial?" O parte din atracţia faţă de întrebare este dată de faptul că marea majoritate a problemelor NP ale căror soluţii necesită timp exponenţial sunt probleme aşa-numite NP-complete, ceea ce înseamnă că o soluţie în timp polinomial la una dintre probleme poate fi adaptată pentru a le rezolva pe toate celelalte. Chiar şi în viaţa reală, problemele NP-complete sunt destul de frecvente, mai ales în marile activităţi planificate. De exemplu, cea mai celebră problema NP-completă  este aşa-numita problemă călătorie-vânzător: având în vedere N oraşe şi distanţele dintre ele, puteţi găsi o rută care să treacă prin toate, dar să fie în acelaşi timp mai mică decât ... o limită oarecare pe care o stabiliţi?

Având în vedere faptul că P probabil nu este egal cu NP - soluţiile eficiente la problemele NP probabil că nu vor fi niciodată găsite - ce este cu toată această agitaţie? Michael Sipser, şeful Departamentului de Matematică al MIT şi membru al Grupului pentru Computaţie Teoretică (TOC) al Laboratorului de Ştiinţa Calculatoarelor şi Inteligenţă Artificială spune că problema P-versus-NP este importantă pentru aprofundarea înţelegerii noastre asupra complexităţii computaţionale.

"O aplicaţie importantă este în domeniul criptografiei", spune Sipser, unde securitatea codurilor de criptare este adesea asigurată de complexitatea unei sarcini de calcul. Sistemul criptografic RSA, care este frecvent utilizat pentru tranzacţii sigure pe Internet - şi a fost inventat la MIT - "este de fapt o consecinţă a studiului complexităţii de a face un anumit număr de calcule teoretice ", spune Sipser.

În mod similar, Sipser spune, "emoţia din jurul computaţiei cuantice a crescut enorm, atunci când Peter Shor" - un alt membru al TOC - "a descoperit o metodă de factorizare a numerelor folosind un computer cuantic. Descoperirea lui Peter a inspirat o cantitate enormă de cercetări, atât în comunitatea informaticienilor, cât şi în comunitatea fizicienilor. "Într-adevăr, pentru un timp, descoperirea lui Shor a stârnit speranţa că nişte calculatoare cuantice, care exploatează proprietăţile contra-intuitive ale particulelor extrem de mici de materie, ar putea rezolva problemele NP-complete în timp polinomial. Dar acest lucru pare puţin probabil acum: problema de factorizare este de fapt una din cele câteva probleme NP grele şi care nu este cunoscută a fi NP-completă.

Sipser spune, de asemenea, că "problema P-versus-NP a devenit recunoscută pe scară largă în comunitatea matematicienilor ca fiind o întrebare matematică fundamentală, importantă şi frumoasă. Cred că a ajutat la crearea unei punţi intre comunităţile matematicienilor şi informaticienilor."

Dar dacă, aşa cum Sipser spune, "complexitatea adaugă o informaţie nouă vechilor probleme" în matematică, ea a schimbat întrebările pe care informatica le pune. "Când te confrunţi cu o nouă  problemă  de calcul", spune Sipser, "ceea ce teoria NP-completitudinii îţi oferă este ca în loc de a-ţi petrece tot timpul în căutarea unui algoritm rapid, îţi poţi petrece jumătate din timp în căutarea unui algoritm rapid şi cealaltă jumătate din timp pentru a căuta o dovadă a NP-completitudinii sale."

Sipser subliniază faptul că unii algoritmi pentru probleme NP-complete prezintă o complexitate exponenţială numai în cel mai rău scenariu; aşadar, într-un caz obişnuit, acestea pot fi mai eficiente decât algoritmii cu timp de execuţie polinomial. Dar chiar şi acolo, NP-completitudinea vă "spune ceva foarte specific", afirmă Sipser. "Aceasta vă spune că, dacă aveţi de gând să căutaţi un algoritm care va funcţiona în fiecare caz şi vă va oferi cea mai bună soluţie, sunteţi condamnaţi: nu încercaţi. Acestea sunt nişte informaţii utile."

 

Articolul reprezintă traducerea articolului Explained: P vs. NP, publicat pe site-ul web.mit.edu.
Traducere: Anamaria Spătaru