Clasele de complexitate P și NP

Clarificări

De exemplu, dacă aveți o problemă și cineva spune "Răspunsul la problema dvs. este setul de numere 1, 2, 3, 4, 5", un computer poate fi capabil, rapid, să își dea seama dacă răspunsul este corect sau greșit, dar poate dura foarte mult timp până când computerul găsește singur "1, 2, 3, 4, 5". Un alt exemplu include găsirea numerelor prime. Este ușor de verificat dacă un număr este prim, dar este foarte dificil să găsești aceste numere în primul rând. Pentru unele întrebări interesante și practice de acest tip, ne lipsește orice modalitate de a găsi rapid un răspuns, dar dacă ni se oferă un răspuns, este posibil să verificăm - adică să verificăm - răspunsul rapid. În acest fel, problemele NP pot fi considerate ca fiind ca niște ghicitori: poate fi greu să găsești răspunsul la o ghicitoare, dar odată ce îl afli, răspunsul pare evident. În această comparație (analogie), întrebarea de bază este: sunt ghicitorile într-adevăr atât de dificile pe cât credem noi că sunt sau ne scapă ceva?

Deoarece aceste tipuri de întrebări P versus NP sunt atât de importante din punct de vedere practic, mulți matematicieni, oameni de știință și programatori de calculatoare doresc să demonstreze propoziția generală conform căreia orice problemă verificată rapid poate fi rezolvată rapid. Această întrebare este suficient de importantă pentru ca Institutul Matematic Clay să ofere 1.000.000 de dolari oricărei persoane care reușește să furnizeze o dovadă sau o explicație validă care să o infirme.

Dacă aprofundăm puțin, vedem că toate problemele P sunt probleme NP: este ușor de verificat dacă o soluție este corectă prin rezolvarea problemei și compararea celor două soluții. Cu toate acestea, oamenii doresc să știe despre opusul: Există alte probleme NP decât problemele P sau toate problemele NP sunt doar probleme P? Dacă problemele NP nu sunt într-adevăr la fel ca problemele P (P ≠ NP), ar însemna că nu pot exista metode generale și rapide de rezolvare a acestor probleme NP, indiferent cât de mult am căuta. Cu toate acestea, dacă toate problemele NP sunt probleme P (P = NP), ar însemna că există metode noi și foarte rapide de rezolvare a problemelor. Doar că nu le-am găsit încă.

Deoarece cele mai bune eforturi ale oamenilor de știință și matematicienilor nu au găsit încă metode generale și ușoare de rezolvare a problemelor NP, mulți oameni cred că există probleme NP altele decât problemele P (adică, că P ≠ NP este adevărat). Cei mai mulți matematicieni cred, de asemenea, că acest lucru este adevărat, dar în prezent nimeni nu a demonstrat acest lucru printr-o analiză matematică riguroasă. Dacă se poate dovedi că NP și P sunt identice (P = NP este adevărat), acest lucru ar avea un impact uriaș asupra multor aspecte ale vieții de zi cu zi. Din acest motiv, întrebarea P versus NP este un subiect important și studiat pe scară largă.

Exemplu

Să presupunem că cineva dorește să construiască două turnuri, prin stivuirea de pietre de masă diferită. Cineva vrea să se asigure că fiecare dintre turnuri are exact aceeași masă. Aceasta înseamnă că va trebui să se așeze rocile în două grămezi care au aceeași masă. Dacă cineva ghicește o împărțire a rocilor care crede că va funcționa, ar fi ușor să verifice dacă a avut dreptate. (Pentru a verifica răspunsul, se pot împărți rocile în două grămezi, apoi se poate folosi o balanță pentru a vedea dacă au aceeași masă). Deoarece este ușor de verificat această problemă, numită "Partiție" de către informaticieni - mai ușor decât să o rezolvi direct, după cum vom vedea - nu este o problemă P. ^[]

Cât de greu este de rezolvat, direct? Dacă se începe cu doar 100 de pietre, există 2^{100-1}-1 = 633.825.300.114.114.700.748.351.602.687, adică aproximativ 6,3 x 10^{29} moduri (combinații) posibile de a împărți aceste pietre în două grămezi. Dacă s-ar putea verifica o combinație unică de roci în fiecare zi, ar fi nevoie de 1,3 x 10^{22} sau de 1.300.000.000.000.000.000.000.000.000.000 de ani de efort. Pentru comparație, fizicienii cred că universul are o vechime de aproximativ 1,4 x 10^{10} ani (450.000.000.000.000.000.000 sau aproximativ 4,5 x 10^{17} secunde, sau aproximativ o trilionime din timpul necesar pentru efortul nostru de a stivui rocile. Aceasta înseamnă că, dacă se ia în considerare tot timpul care a trecut de la începutul universului, ar trebui să se verifice mai mult de două trilioane (2 000 000 000 000 000 000) de moduri diferite de împărțire a rocilor în fiecare secundă, pentru a verifica toate modurile diferite.

Dacă s-ar programa un calculator puternic, pentru a testa toate aceste moduri de împărțire a rocilor, s-ar putea verifica 1 000 000 de combinații pe secundă folosind sistemele actuale. Aceasta înseamnă că ar fi nevoie de 2 000 000 000 {\displaystyle 2 000 000 000} de calculatoare foarte puternice, care să funcționeze de la originea universului, pentru a testa toate modalitățile de împărțire a rocilor.

Cu toate acestea, ar putea fi posibilă găsirea unei metode de împărțire a rocilor în două grămezi egale fără a verifica toate combinațiile. Întrebarea "Este P egal cu NP?" este o prescurtare pentru a întreba dacă poate exista o astfel de metodă.

De ce este important

Există multe probleme importante ale NP pe care oamenii nu știu cum să le rezolve într-un mod mai rapid decât testarea tuturor răspunsurilor posibile. Iată câteva exemple:

• Un vânzător ambulant dorește să viziteze 100 de orașe cu mașina, începând și terminând călătoria acasă. El are o rezervă limitată de benzină, așa că poate parcurge în total doar 10 000 de kilometri. El vrea să știe dacă poate vizita toate orașele fără să rămână fără benzină.
• O școală oferă 100 de clase diferite, iar un profesor trebuie să aleagă o oră pentru examenul final al fiecărei clase. Pentru a preveni copiatul, toți elevii care frecventează un curs trebuie să susțină examenul pentru acel curs în același timp. Dacă un elev urmează mai multe cursuri, atunci toate examenele trebuie să aibă loc la ore diferite. Profesorul dorește să știe dacă poate programa toate examenele în aceeași zi, astfel încât fiecare elev să poată susține examenul pentru fiecare clasă.
• Un fermier vrea să ducă la piață 100 de pepeni de diferite mase. Trebuie să împacheteze pepenii în cutii. Fiecare cutie poate conține doar 20 de kilograme fără să se spargă. Fermierul trebuie să știe dacă 10 cutii îi vor fi suficiente pentru a transporta toți cei 100 de pepeni la piață. (Acest lucru este banal, dacă nu mai mult de un pepene verde cântărește mai mult de 2 kg, atunci oricare 10 poate fi pus în fiecare dintre cutii, dacă nu mai mult de zece pepeni cântărește mai mult de 2 kg, atunci câte unul din fiecare dintre ei poate fi pus în fiecare cutie, etc., pentru o soluție rapidă; observația va fi cheia oricărei soluții rapide, cum ar fi aceasta sau problema setului de numere).
• O mare galerie de artă are mai multe camere, iar fiecare perete este acoperit cu multe picturi scumpe. Proprietarul galeriei vrea să cumpere camere de luat vederi pentru a supraveghea aceste tablouri, în cazul în care un hoț încearcă să fure vreunul dintre ele. Vrea să știe dacă 100 de camere îi vor fi suficiente pentru a se asigura că fiecare tablou poate fi văzut de cel puțin o cameră.
• Problema clicii: Directorul unei școli are o listă cu elevii care sunt prieteni între ei. Dorește să găsească un grup de 10% dintre elevi care sunt toți prieteni între ei.

Timp exponențial

În exemplul de mai sus, vedem că, cu 100 {\displaystyle 100} de pietre, există 2 100 {\displaystyle 2^{100}} moduri de a împărți setul de pietre. Cu n {\displaystyle n} roci, există 2 n {\displaystyle 2^{n}} combinații. Funcția f ( n ) = 2 n {\displaystyle f(n)=2^{n}} este o funcție exponențială. Este importantă pentru NP deoarece modelează cel mai rău caz numărul de calcule necesare pentru a rezolva o problemă și, prin urmare, cel mai rău caz de timp necesar.

Și până acum, pentru problemele dificile, soluțiile au necesitat de ordinul a 2 n {\displaystyle 2^{n}} calcule. Pentru orice problemă specifică, oamenii au găsit modalități de a reduce numărul de calcule necesare. Cineva ar putea găsi o modalitate de a face doar 1% din numărul de calcule în cel mai rău caz și să economisească o mulțime de calcule, dar asta înseamnă tot 0,01 × ( 2 n ) {\displaystyle 0,01\ ori (2^{n})} calcule. Și fiecare piatră în plus încă dublează numărul de calcule necesare pentru a rezolva problema. Există perspective care pot produce metode pentru a efectua chiar mai puține calcule, producând variații ale modelului: de exemplu, 2 n / n 3 {\displaystyle 2^{n}/n^{3}}. . Dar funcția exponențială continuă să domine pe măsură ce n {\displaystyle n} crește.

Luați în considerare problema programării examenelor (descrisă mai sus). Dar să presupunem, în continuare, că există 15000 de studenți. Există un program de calculator care preia orarele tuturor celor 15000 de studenți. Acesta rulează într-o oră și produce un program de examene astfel încât toți studenții să-și poată face examenele într-o săptămână. Acesta respectă o mulțime de reguli (nu se pot da examene consecutive, nu se pot da mai mult de 2 examene în orice perioadă de 28 de ore, ...) pentru a limita stresul din săptămâna examenelor. Programul rulează timp de o oră în pauza de la jumătatea semestrului și toată lumea își cunoaște programul de examene cu suficient timp pentru a se pregăti.

În anul următor, însă, sunt cu 10 studenți în plus. Dacă același program rulează pe același calculator, atunci acea oră se va transforma în 2 10 {\displaystyle 2^{10}} ore, deoarece fiecare elev în plus dublează calculele. Asta înseamnă 6 {\displaystyle 6} săptămâni! Dacă ar fi fost 20 de studenți în plus, atunci

2 20 {\displaystyle 2^{20}} ore = 1048576 {\displaystyle 1048576}ore ~ 43691 {\displaystyle 43691} zile ~ 113 {\displaystyle 113} ani

Astfel, pentru 15000 {\displaystyle 15000} de elevi, este nevoie de o oră. Pentru 15020 {\displaystyle 15020} studenți, este nevoie de 113 {\displaystyle 113} ani.

După cum puteți vedea, funcțiile exponențiale cresc foarte repede. Majoritatea matematicienilor consideră că cele mai dificile probleme NP necesită un timp exponențial pentru a fi rezolvate.

Probleme NP-complete

Matematicienii pot demonstra că există unele probleme NP care sunt NP-complete. O problemă NP-Completă este cel puțin la fel de dificil de rezolvat ca orice altă problemă NP. Acest lucru înseamnă că, dacă cineva a găsit o metodă pentru a rezolva rapid orice problemă NP-Completă, ar putea folosi aceeași metodă pentru a rezolva rapid orice problemă NP. Toate problemele enumerate mai sus sunt NP-Complete, astfel încât, dacă vânzătorul a găsit o modalitate de a-și planifica rapid călătoria, i-ar putea spune profesoarei, iar aceasta ar putea folosi aceeași metodă pentru a programa examenele. Fermierul ar putea folosi aceeași metodă pentru a determina de câte cutii are nevoie, iar femeia ar putea folosi aceeași metodă pentru a găsi o modalitate de a-și construi turnurile.

Deoarece o metodă care rezolvă rapid una dintre aceste probleme le poate rezolva pe toate, există mulți oameni care doresc să găsească una. Cu toate acestea, deoarece există atât de multe probleme NP-Complete diferite și nimeni nu a găsit până în prezent o modalitate de a rezolva rapid măcar una dintre ele, majoritatea experților consideră că rezolvarea rapidă a problemelor NP-Complete nu este posibilă.

Proprietăți de bază

În teoria complexității computaționale, clasa de complexitate NP-completă (prescurtat NP-C sau NPC), este o clasă de probleme care are două proprietăți:

• Aceasta face parte din setul de probleme NP (non-deterministic polynomial time): Orice soluție dată a problemei poate fi verificată rapid (în timp polinomial).
• De asemenea, se regăsește în setul de probleme NP-hard: Cele care sunt cel puțin la fel de dificile ca și cele mai dificile probleme din NP. Problemele care sunt NP-hard nu trebuie să fie elemente ale NP; într-adevăr, ele pot să nu fie nici măcar decidabile.

Prezentare formală

NP-complet este un subansamblu al lui NP, setul tuturor problemelor de decizie ale căror soluții pot fi verificate în timp polinomial; NP poate fi definit în mod echivalent ca setul de probleme de decizie rezolvate în timp polinomial pe o mașină. O problemă p din NP este, de asemenea, în NPC dacă și numai dacă orice altă problemă din NP este transformată în p în timp polinomial. NP-complet urma să fie folosit ca adjectiv: problemele din clasa NP-complet erau ca probleme NP+complete.

Problemele NP-complete sunt studiate deoarece capacitatea de a verifica rapid soluțiile la o problemă (NP) pare să fie corelată cu capacitatea de a rezolva rapid o problemă (P). S-a constatat că orice problemă din NP se rezolvă rapid - așa cum se numește setul de probleme P = NP:. Singura problemă din NP-complet este rezolvată rapid, mai rapid decât orice problemă din NP, de asemenea rezolvată rapid, deoarece definiția unei probleme NP-complete prevede că orice problemă din NP trebuie să fie rapid reductibilă la orice problemă din NP-complet (se reduce în timp polinomial). [1]

Exemple

Problema satisfacției booleene este cunoscută ca fiind NP completă. În 1972, Richard Karp a formulat 21 de probleme care sunt cunoscute ca fiind NP-complete. Acestea sunt cunoscute sub numele de cele 21 de probleme NP-complete ale lui Karp. Printre acestea se numără probleme precum problema programării numerelor întregi, care aplică tehnici de programare liniară la numere întregi, problema knapsack sau problema acoperirii vertexurilor.