Cea mai mare problemă din informatică: P versus NP

Există șapte probleme de matematică despre care s-a spus că sunt atât de grele și de interesante, încât Institutul de Matematică Clay le-a numit problemele mileniului, iar cine rezolvă oricare dintre ele primește un premiu de un milion de dolari. Una dintre probleme ține și de informatică și se numește problema P versus NP. Hai să vedem despre ce este vorba, de fapt.

Să nu ne amăgim că va fi simplu de explicat. Doar e o problemă a mileniului. Așa că du-te să-ți faci un ceai verde bun 🍵 și să începem. Mai întâi vom vedea patru probleme diferite din lumea informaticii și a algoritmilor. Le vom analiza și vom vedea ce legătură au cu literele P și NP.

Problema nr. 1: Găsirea celui mai mic număr

P vs. NP ține de algoritmi și de complexitatea lor. Imaginează-ți că aș răsturna în fața ta o sută de bilețele, pe fiecare ar fi scris câte un număr, și te-aș ruga să-mi găsești biletul pe care este scris cel mai mic număr. Cât îți va lua?

Jumătate de minut? Două minute?

Astea sunt unități de timp care nu ne prea interesează în informatica teoretică. Ne interesează mai degrabă numărul de operații. Putem deci să întrebăm altfel: câte bilețele trebuie să verific ca să fiu sigur că am găsit cel mai mic număr? Răspunsul este că trebuie să verific toate bilețelele – pentru că cel mai mic număr poate fi chiar pe ultimul bilețel. Dacă îți arunc în față o sută de bilețele, trebuie să verifici o sută de bilețele. Dacă îți arunc o mie, trebuie să verifici o mie. În general, dacă îți arunc n bilețele, trebuie să verifici n bilețele.

Asta se numește complexitatea algoritmilor. Dacă îți arunc n bilețele și tu trebuie să faci n operații ca să găsești cel mai mic număr, înseamnă că acest algoritm de căutare a celui mai mic număr are complexitatea n, numită și complexitate liniară, pentru că ea este descrisă de o funcție de gradul întâi.

Bine, ai parcurs o sută de bilețele și ai anunțat că cel mai mic număr este 17. Cum pot verifica eu că spui adevărul? Nu există altă cale decât să parcurg din nou toate bilețelele și să verific că pe niciunul nu e un număr mai mic. Adică tu trebuie să te uiți la n bilețele ca să găsești cel mai mic număr, iar eu, când vreau să verific, trebuie să fac același lucru. Complexitatea verificării rezultatului este deci tot n, complexitate liniară.

Există algoritmi la care e mai simplu să verifici rezultatul decât să-l găsești?

Problema nr. 2: Produsul unei perechi

Imaginează-ți că îți răstorn în față două grămezi de aceeași mărime de bilețele, pe fiecare bilețel fiind din nou câte un număr. Și acum aș vrea să găsești un număr din grămada A și un număr din grămada B astfel încât produsul lor să fie 918. De exemplu, să avem grămezile de numere:

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

Cum putem găsi perechea de numere al cărei produs să fie egal cu 918? Păi, pur și simplu putem încerca toate posibilitățile. Câte or fi? Destul de multe, vor fi 25. Începem înmulțind primul număr din grămada A, adică 49, cu fiecare număr din grămada B:

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

Nicio pereche de numere nu duce la 918. Încercăm deci același lucru cu celelalte numere din grămada A, adică încă cinci perechi pentru numărul 11, încă cinci perechi pentru numărul 32, încă cinci perechi pentru 54 și ultimele cinci perechi pentru 15. În total putem încerca 25 de perechi de numere. În final aflăm că 54 · 17 = 918.

Care este complexitatea acestui algoritm? Ne va interesa câte perechi de numere a trebuit să înmulțim. Ambele grămezi conțineau câte cinci bilețele, iar noi a trebuit să încercăm fiecare dintre cele cinci numere din prima grămadă cu fiecare dintre cele cinci numere din a doua. În total am încercat 5 · 5 = 25 de combinații. Dacă ți-aș arunca în față două grămezi de câte 10 bilețele, ar trebui să încerci 10 · 10 = 100 de combinații. Generalizând, dacă îți arunc în față două grămezi de câte n bilețele, trebuie să încerci n · n = n² combinații.

Spunem că acest algoritm al nostru are complexitatea n², complexitate pătratică, pentru că este descrisă de o funcție de gradul al doilea.

Cât de greu va fi însă să verificăm rezultatul? Dacă îmi răspunzi că 54 și 17 sunt numerele al căror produs este 918, nu mai trebuie să parcurg toate perechile de numere din ambele grămezi, așa cum a trebuit să faci tu. Îmi ajunge să înmulțesc această singură pereche, 54 · 17, și voi ști dacă ai dreptate sau nu. Așadar, în timp ce pentru rezolvarea acestei probleme trebuie calculate până la n² produse, pentru verificare este suficient să calculăm un singur produs. Verificarea are deci complexitate constantă, 1.

Prin asta, această problemă se deosebește mult de cea precedentă, unde aveam nevoie de tot atâția pași și pentru calcul, și pentru verificarea ulterioară.

Această problemă este, de asemenea, mult mai complexă, ca ordin de mărime, decât cea precedentă. Dacă ți-aș răsturna în față zece mii de bilețele și ți-aș cere să găsești cel mai mic număr, probabil l-ai găsi într-o zi. Dar dacă ți-aș răsturna de două ori zece mii de bilețele și te-aș pune să cauți produsul, ar trebui să verifici zece mii ori zece mii de produse, adică o sută de milioane de calcule. Chiar dacă ai încerca un produs pe secundă, te-ar costa cam trei ani.

Problema nr. 3: Suma unei submulțimi

Să vedem a treia problemă. De data aceasta îți răstorn în față douăsprezece bilețele cu numere și aș vrea să găsești oricâte bilețele a căror sumă este zero. De exemplu:

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

Alege din aceste numere un grup oarecare de numere a căror sumă este 0. De exemplu, numerele

$24 + 48 - 69 + 1$

dau suma 4, deci nu sunt un răspuns corect. Răspunsul corect este grupul de numere… și știi ce? Încearcă să-l găsești singur, ca temă pentru acasă 😉. Există un singur grup de numere a căror sumă este 0. Măcar vei vedea cât de grea este această problemă.

Acum trebuie să aflăm complexitatea acestei probleme. Calculul în sine nu mai este chiar banal și e mai degrabă pentru pasionați. Dacă te interesează cum se poate calcula complexitatea acestei probleme, citește mai departe. Altfel, poți sări la capitolul următor. ⏩

Cum putem găsi, așadar, un grup de numere a căror sumă este 0? Păi, trebuie pur și simplu să încercăm toate combinările posibile de numere. Trebuie să încercăm toate perechile de numere, toate tripletele, grupurile de patru, de cinci etc., și la fiecare grup trebuie să verificăm dacă suma lui este zero. Câte astfel de combinații există?

Să vedem asta pe o mulțime mai mică de numere. Câte grupuri diferite de numere, adică submulțimi, pot forma din numerele B = {5, 7, 9}? În total sunt opt:

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

Observă că am numărat și submulțimea vidă B₁. Acum nu prea ne ajută, dar am lăsat-o acolo ca să fie totul în regulă. Ca să ne simplificăm calculul, vom asocia fiecărei submulțimi un vector binar. Un vector binar este pur și simplu un șir de zerouri și unu, de exemplu 00101010. Noi vom lucra cu vectori binari de lungime trei. Asociem vectorul 101 submulțimii care conține „primul și al treilea număr din mulțimea inițială, dar nu și al doilea”, adică mulțimii {5, 9}. Vectorul 110 îl asociem submulțimii care conține „primul și al doilea număr din mulțimea inițială, dar nu și al treilea”, adică mulțimii {5, 7} și așa mai departe.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

Vedem că fiecare submulțime are exact un vector binar de lungime trei. Și fiecare vector binar de lungime trei corespunde exact unei submulțimi. Așadar, dacă aflăm câți vectori binari diferiți de lungime n există, obținem numărul de combinații diferite pe care le putem forma când avem la intrare n numere diferite. Hai să calculăm.

Vectori binari de lungime unu există doi: 0 și 1.

Vectorii binari de lungime doi îi obținem luând toți vectorii binari de lungime unu și adăugând la sfârșitul fiecăruia un 0: obținem vectorii 00 și 10. Luăm din nou toți vectorii de lungime 1 și adăugăm la sfârșit un 1: 01 și 11. Astfel am obținut toți vectorii de lungime 2: 00, 01, 10 și 11.

Vectorii binari de lungime trei îi obținem luând toți vectorii binari de lungime doi și adăugând la sfârșit un zero: 000, 010, 100 și 110, și un unu: 001, 011, 101 și 111.

Și tot așa pentru fiecare lungime următoare. Vedem că dacă mărim lungimea vectorului binar cu unu, numărul de vectori binari diferiți se dublează. Pentru lungimea patru am obține deci în total 2 · 2 · 2 · 2, adică 16 combinații diferite.

În general putem deduce că, dacă avem o mulțime M cu n elemente, atunci numărul tuturor submulțimilor acestei mulțimi M este egal cu numărul tuturor vectorilor binari diferiți de lungime n, iar acesta este egal cu

$\underset{de n ori}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ sau n² – nu e totuna? Tot un drac? 🤷‍♂

Există deci 2ⁿ submulțimi diferite pe care le putem forma dintr-o mulțime de n numere. În cazul nostru avem n = 12 numere și trebuie să verificăm deci 2¹² combinații diferite, adică 4096 de combinații. Spunem că această problemă are complexitatea 2ⁿ, complexitate exponențială, pentru că este descrisă de o funcție exponențială.

Observă că problema precedentă avea complexitatea n², în timp ce aceasta are complexitatea 2ⁿ. Arată foarte asemănător, nu-i așa? Numai că e o mare diferență între situația în care exponentul este constant și cea în care apare variabila n. Observă că pentru n = 4 obținem

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

Bine, deocamdată ne iese la fel. Dar dacă n = 10?

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

Hopa, funcția exponențială a țâșnit și e deodată de aproape zece ori mai mare decât cea pătratică. Ce obținem pentru n = 20?

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1.048 .576 \end{array}$

Complexitatea exponențială are pentru n = 20 o valoare de aproximativ 2600 de ori mai mare decât complexitatea pătratică. Vedem deci că funcția exponențială crește mult mai repede decât funcția de gradul al doilea. Adu-ți aminte de asta data viitoare când ne lovește vreo pandemie care se răspândește în populație cu viteză exponențială.

Dacă ți-aș arunca deci în față douăzeci de bilețele, ar trebui să verifici 1.048.576 de combinații. E destul de mult.

Cum verificăm corectitudinea rezultatului?

Cât timp îmi va lua să verific că grupul de numere găsit chiar are suma 0? Va fi destul de rapid: adun pur și simplu acest grup de numere și, dacă suma lui este 0, ai găsit grupul corect de bilețele, iar dacă suma este alta, ai găsit un set greșit.

Vedem din nou că verificarea rezultatului este cu un ordin de mărime mai simplă decât găsirea lui.

Problema nr. 4: Problema comis-voiajorului

Problema comis-voiajorului este una dintre cele mai faimoase probleme de algoritmi. Pe scurt, avem un comis-voiajor care vinde ploaie. Și acest comis-voiajor trebuie să călătorească mult ca să-și câștige existența. Așa că a hotărât să viziteze 14 orașe mari din România. Și, pentru că nu vrea să risipească, a hotărât să găsească cel mai scurt drum posibil care să-l ducă prin toate aceste orașe. Iar sarcina noastră este să găsim acest cel mai scurt drum.

Cum putem găsi cel mai scurt drum? Încercăm toate posibilitățile.

Putem simplifica lucrurile. Să ne imaginăm că între oricare două orașe există exact un cel mai scurt drum. Cum putem găsi cel mai scurt drum care trece prin toate orașele? Avem 14 orașe. Avem deci 14 posibilități de a alege de unde să începem. Să zicem că am început din Cluj-Napoca!!! Unde putem ajunge din Cluj-Napoca? Teoretic, putem merge în oricare alt oraș. Putem alege deci dintre cele 13 orașe rămase.

Putem deja calcula că avem în total 14 · 13 posibilități de a vizita primele două orașe – avem 14 posibilități de a alege de unde începem, iar apoi putem alege dintre cele 13 orașe rămase.

Când ajungem în al doilea oraș, trebuie să mergem mai departe. În două orașe am fost deja, deci putem pleca spre unul dintre cele 12 orașe rămase. Avem astfel în total 14 · 13 · 12 posibilități de a vizita primele trei orașe.

După ce vizităm al treilea oraș, trebuie să alegem unul dintre cele 11 orașe rămase, apoi unul dintre cele 10 orașe rămase și așa mai departe.

Când le-am vizitat pe toate, vom afla că am avut de ales în total dintre

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

posibilități. Asta îți poate aminti de factorial, pe care îl notăm cu semnul exclamării. Putem spune deci că acest produs este egal cu 14!:

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

și, prin urmare, există 14! drumuri care trec prin toate cele 14 orașe. E mult? Destul de mult, pentru că

$14! = 87.178 .291 .200 .$

În general, dacă am căuta cel mai scurt drum între n orașe, ar trebui să încercăm n! drumuri diferite. Complexitatea acestei rezolvări este deci n!.

Cum am verifica dacă am găsit rezultatul corect? Dacă mi-ai spune că cel mai scurt drum este din Timișoara la Cluj-Napoca, apoi la Brașov și așa mai departe, cum pot verifica eu că spui adevărul? Păi, cam greu 🤷‍♂. Pentru că, uitându-mă la acel drum, nu am cum să verific ușor dacă tocmai acesta este cel mai scurt. De fapt, trebuie să refac întregul calcul. Verificarea rezultatului are deci tot complexitatea n!.

Clasele P și NP

Am văzut patru probleme și algoritmii care le rezolvă și am analizat cât de greu este să găsești soluția și cât de greu este să verifici această soluție. Le putem rezuma în tabelul următor:

Problema	Complexitatea rezolvării	Complexitatea verificării
Cel mai mic număr	n	n
Produsul unei perechi	n²	1
Suma unei submulțimi	2ⁿ	n
Comis-voiajorul	n!	n!

Acum vom împărți problemele noastre în două grupe. Prima grupă o vor forma problemele care sunt simple de rezolvat. Sunt problemele care se pot rezolva cu complexitatea n sau n² sau n³ sau n⁴ etc. Pentru că expresii precum n² se numesc polinoame, această clasă de probleme se notează cu litera P. Spunem deci că clasa P conține problemele care se pot rezolva în timp polinomial (= au complexitatea de pildă n² sau n⁷). În general, sunt problemele care se pot rezolva mai mult sau mai puțin ușor.

În clasa P intră deci problema nr. 1, găsirea celui mai mic număr, pentru că are complexitatea rezolvării n, și apoi problema nr. 2, produsul unei perechi, pentru că complexitatea rezolvării ei este n², ambele fiind polinoame.

A doua clasă este clasa NP. Ea conține problemele care se pot verifica în timp polinomial. În clasa NP intră deci toate problemele, în afară de ultima. Problema comis-voiajorului nu o putem verifica în timp polinomial. Cele trei probleme precedente se pot verifica în timp polinomial.

Problema comis-voiajorului nu o putem nici rezolva, nici verifica în timp polinomial. Pentru ea am avea deci nevoie de o altă clasă, care să conțină probleme și mai grele. Această clasă există, dar deocamdată nu ne interesează.

Este evident că clasa P este o submulțime a clasei NP. Adică orice problemă din clasa P este totodată în clasa NP. Are sens – dacă putem rezolva o problemă în timp polinomial, putem și verifica rezultatul în timp polinomial.

Problema P vs. NP

Și este valabil și invers? Este orice problemă din clasa NP și în clasa P? Adică, dacă există o metodă de a verifica rezultatul unei probleme în timp polinomial, există și un algoritm care ar rezolva problema respectivă în timp polinomial?

De exemplu, știm că putem verifica rezultatul problemei nr. 3, suma unei submulțimi, în timp polinomial. Dar pentru rezolvarea ei am folosit un algoritm care nu este polinomial, algoritmul folosit are complexitate exponențială 2ⁿ. Știm însă sigur că pentru această problemă nu există niciun algoritm cu complexitate polinomială?

Nu știm!

Ar putea foarte bine să se întâmple ca, pentru orice problemă care se poate verifica în timp polinomial, să existe un algoritm care rezolvă problema în timp polinomial. Noi nu știm. Nu putem demonstra existența unui astfel de algoritm, dar nu putem nici infirma existența lui.

Dacă pentru fiecare problemă din clasa NP ar exista un algoritm care o rezolvă în timp polinomial, ar însemna că clasa NP este de fapt egală cu clasa P. Toate problemele din clasa P ar fi în clasa NP, iar toate problemele din clasa NP ar fi în clasa P – cele două clase ar fi egale, identice.

Problema P vs. NP este deci întrebarea dacă clasa P este identică cu clasa NP sau dacă este vorba despre două clase diferite de probleme.

Fie deci P = NP, fie P ≠ NP. Asta nu știe nimeni, iar dacă tu descoperi răspunsul, te așteaptă un premiu de un milion de dolari, glorie nemuritoare și, probabil, și premiul Turing, care e un fel de premiu Nobel pentru informaticieni.

Ce s-ar întâmpla dacă P = NP?

Ce s-ar întâmpla dacă ar fi adevărat că P = NP? Păi, nu e chiar simplu de spus ce s-ar întâmpla. Am ști că pentru toate problemele din clasa NP există un algoritm care le rezolvă în timp polinomial. De exemplu, că pentru problema noastră nr. 3, suma unei submulțimi, există un algoritm care o rezolvă în timp polinomial. Numai că asta are trei capcane:

Faptul că am ști că un astfel de algoritm există nu înseamnă că suntem în stare să-l găsim. Am ști pur și simplu că da, există un algoritm care rezolvă problema în timp polinomial, dar poate că nu am ști să-l construim încă o sută de ani. E ceva asemănător cu faptul că teoria generală a relativității a prezis existența găurilor negre, dar ne-au trebuit totuși câteva decenii în plus până să reușim să facem prima „fotografie” a unei găuri negre.
Faptul că există un algoritm care lucrează în timp polinomial nu înseamnă, din păcate, că este rapid. Am putea găsi un algoritm cu complexitatea n¹⁰⁰. Pentru că și expresia n¹⁰⁰ este un polinom. Dacă comparăm complexitățile 2ⁿ și n¹⁰⁰, vedem că, atâta timp cât n este relativ mic, algoritmul cu complexitatea 2ⁿ are nevoie încă de mai puține operații. De exemplu, pentru n = 20 avem 2²⁰ = 1.048.576, în timp ce 20¹⁰⁰ duce la un număr cu aproximativ 130 de cifre, un număr cu 120 de ordine de mărime mai mare decât 1.048.576. Algoritmul nostru polinomial ar fi deci, în realitate, mai lent decât cel exponențial. Cel puțin atâta timp cât n este relativ mic.
Dacă am reuși totuși să găsim un algoritm rapid care lucrează în timp polinomial, am putea rezolva multe probleme mai repede și cu mai mare precizie. Asta este, desigur, o veste bună, dar are și părți negative. Există un domeniu care se bazează pe faptul că unele probleme sunt greu de rezolvat, iar acesta este criptografia – criptarea. S-ar putea ca spargerea cifrurilor actuale să devină cu un ordin de mărime mai simplă.

Intermezzo: pentru că ai citit până aici, îți dezvălui drept recompensă că soluția problemei nr. 3 este 24 + 1 − 60 + 16 − 83 + 48 + 54.

Ce s-ar întâmpla dacă P ≠ NP?

Dacă ar fi adevărat că clasele de probleme P și NP sunt diferite, nu s-ar întâmpla prea multe, pentru că asta este mai mult sau mai puțin status quo-ul. În prezent nu avem niciun algoritm care să rezolve în timp polinomial vreo problemă grea din NP, iar dacă cineva ar demonstra că P ≠ NP, așa ar rămâne pentru totdeauna. Mult mai mare senzație ar fi o demonstrație că P = NP.

Referințe în cultura populară

Într-un episod din Familia Simpson putem vedea că Homer ajunge într-un fel de realitate alternativă, în care i se arată că P = NP. Poți vedea pe youtube.com.
În Futurama, în schimb, putem vedea că au în depozit două dosare, unul cu numele P și altul cu numele NP. Poți vedea pe youtube.com.
Al doilea episod din sezonul al doilea al serialului Elementary, intitulat „Solve for X”, are ca temă uciderea unui matematician care probabil rezolvase problema P versus NP.

« Anterior: Cât face 1 + 2 + 5 · 0?

Următor: Metoda Trachtenberg de adunare rapidă »