dreapta|miniatura|300x300px|Diagramă Euler pentru mulțimile de probleme P, NP, NP-complete, și NP-dure. Partea stângă este valabilă în ipoteza că P≠NP, în timp ce partea dreaptă este valabilă în ipoteza că P=NP (cu excepția faptului că limbajul vid și complementul acestuia nu sunt NP-complete) În teoria complexității, o problemă de decizie este NP-completă atunci când este atât în NP cât și în NP-hard. Mulțimea problemelor NP-complete este adesea notată cu NP-C sau NPC. Abrevierea NP se referă la „timp nedeterminist polinomial”.
Deși orice soluție la o problemă NP-completă poate fi verificată rapid (în timp polinomial), nu este cunoscut niciun mod eficient de a găsi o soluție dacă nu se cunoaște una; într-adevăr, cea mai notabilă caracteristică a problemelor NP-complete este faptul că nu se cunoaște nicio soluție rapidă pentru ele. Aceasta înseamnă că timpul necesar pentru a rezolva problema folosind orice algoritm cunoscut în prezent crește foarte repede cu dimensiunea problemei. Ca urmare, problema stabilirii dacă este posibil să se rezolve aceste probleme rapid, numită problema P versus NP, este una dintre principalele probleme nerezolvate în informatică astăzi.
Deși înca nu s-a descoperit o metodă de calcul a soluțiilor pentru problemele NP-complete folosind un timp rezonabil, informaticieni și programatori încă se confruntă frecvent cu probleme NP-complete. Problemele NP-complete sunt adesea rezolvate prin utilizarea metodelor euristice și a .
Generalități Problemele NP-complete sunt în NP, mulțimea tuturor problemelor de decizie ale căror soluții pot fi verificate în timp polinomial; NP poate fi definită echivalent ca mulțimea problemelor de decizie care pot fi rezolvate în timp polinomial pe o mașină Turing nedeterministă. O problemă p din NP este NP-completă dacă orice altă problemă din NP poate fi transformată (sau redusă), la p în timp polinomial.
Problemele NP-complete sunt studiate deoarece capacitatea de a verifica rapid soluții la o problemă (NP) pare a fi corelată cu capacitatea de a rezolva rapid problema (P). Nu se știe dacă fiecare problemă din NP poate fi rezolvată rapid—aceasta se numește problema P versus NP. Dar dacă orice problemă NP-completă poate fi rezolvată rapid, atunci se pot rezolva rapid toate problemele din NP, pentru că definiția unei probleme NP-complete afirmă că fiecare problemă din NP este ușor reductibilă la orice problemă NP-completă („ușor reductibilă” cu sensul că poate fi redusă în timp polinomial). Din acest motiv, se spune adesea că problemele NP-complete sunt mai grele sau mai dificile decât problemele NP, în general.
Definiție formală a NP-completitudinii O problemă de decizie este NP-completă dacă: este în NP, și Toate problemele din NP sunt la în timp polinomial. este în NP demonstrând că o soluție candidat la poate fi verificată în timp polinomial.
O problemă care satisface condiția 2 este declarată a fi NP-dură, indiferent dacă îndeplinește sau nu condiția 1.
O consecință a acestei definiții este că, dacă ar exista un algoritm în timp polinomial (pe o , sau pe orice altă mașină abstractă Turing-echivalentă) pentru s-ar putea rezolva toate problemele din NP în timp polinomial.
Context Conceptul de NP-completitudine a fost introdus în 1971 (a se vedea ), deși termenul NP-complet a fost introdus mai târziu. În conferința din 1971, a existat o dezbatere aprinsă între informaticieni despre dacă problemele NP-complete pot fi rezolvate în timp polinomial pe o mașină Turing deterministă. John Hopcroft a adus pe toți cei prezenți la conferință la un consens că întrebarea dacă problemele NP-complete sunt rezolvabile în timp polinomial ar trebui amânată pentru o dată ulterioară, deoarece nimeni nu avea nicio demonstrație formală pentru afirmațiile sale, oricare ar fi fost acelea. Atunci s-a născut întrebarea dacă P=NP.
Nimeni nu a fost încă în măsură să determine dacă problemele NP-complete sunt, de fapt, rezolvabile în timp polinomial, ceea ce a făcut ca aceasta să fie una dintre marile probleme nerezolvate din matematică. oferă un 1 milion de dolari recompensă pentru oricine demonstrează că P=NP sau că P≠NP.
afirmă că problema satisfiabilității booleene este NP-completă (este disponibilă simplă, dar încă foarte tehnică). În 1972, Richard Karp a demonstrat că sunt mai multe alte probleme NP-complete (a se vedea cele 21 de probleme NP-complete ale lui Karp); astfel, există o clasă de probleme NP-complete (pe lângă problema satisfiabilități booleene). De la rezultatele inițiale, mii de alte probleme s-au dovedit a fi NP-complete prin reducere la alte probleme, anterior demonstrate a fi NP-complete; multe dintre aceste probleme sunt colectate în cartea lui și din 1979 intitulată . Pentru mai multe detalii, consultați Introducere în Proiectarea și Analiza Algoritmilor de Anany Levitin.
Probleme NP-complete dreapta|miniatura|Unele probleme NP-complete, cu indicarea reducerilor folosite de obicei pentru a le demonstra NP-completitudinea Un exemplu interesant este cel , problema din teoria grafurilor de a determina dacă există un izomorfism de grafuri între două grafuri. Două grafuri sunt izomorfe dacă unul poate fi transformat în celălalt pur și simplu prin redenumirea nodurilor. Fie aceste două probleme: Izomorfismul de grafuri: Este un graf G1 izomorf cu graful G2? Izomorfismul de subgrafuri: Este un graf G1 izomorf cu un subgraf al grafului G2? Problema izomorfismului de subgrafuri este NP-completă. Problema izomorfismului de grafuri problema este suspectată a nu fi nici în P, nici NP-completă, deși este în NP. Acesta este un exemplu de problemă care este considerată a fi grea, dar nu este considerată a fi NP-completă.
Cel mai simplu mod de a demonstra că o problema nouă este NP-completă este de a demonstra mai întâi că este în NP, și apoi de a o reduce la o problemă NP-completă cunoscută. Prin urmare, este utilă cunoașterea unei mulțimi de probleme NP-complete. Lista de mai jos conține unele probleme NP-complete bine-cunoscute atunci când sunt exprimate ca probleme de decizie.
Problema satisfiabilității booleene (SAT) Problema rucsacului Problema lanțului hamiltonian Problema comis-voiajorului (varianta deciziei)
Problema clicii
Problema colorării grafului
La dreapta este o diagramă cu unele dintre probleme și reducerile folosite de obicei pentru a le demonstra NP-completitudinea. În această diagramă, o săgeată de la o problemă la alta indică direcția de reducere. Această diagramă este însă înșelătoare ca descriere a relației matematice dintre aceste probleme, deoarece există o reducere în timp polinomial între oricare două probleme NP-complete; dar se indică aici doar acolo unde demonstrația acestei reduceri în timp polinomial a fost mai simplă.
Există de multe ori doar o mică diferență între o problemă din P și una NP-completă. De exemplu, problema 3-satisfiabilității problema, o restrângere a problemei satisfiabilității booleene, rămâne NP-completă, pe când problema ușor mai restrânsă a este în P (în special, ), iar problema mai generală, max. 2-sat. este iarăși NP-completă. Determinarea dacă un graf poate fi colorat în 2 culori este în P, dar în 3 culori este NP-completă, chiar și atunci când este limitată la grafuri planare. Determinarea dacă un graf este sau este bipartit este foarte ușoară (în L), dar găsirea unui subgraf bipartit maxim sau a unui subgraf ciclic maxim este NP-completă. O soluție pentru problema rucsacului la orice procent fix din soluția optimă poate fi calculată în timp polinomial, dar găsirea soluției optime este NP-completă.
Rezolvarea problemelor NP-complete În prezent, toți algoritmii cunoscuți pentru probleme NP-complete necesită timp superpolinomial în raport cu mărimea intrării, și nu se cunoaște dacă există algoritmi mai rapizi.
Următoarele tehnici se pot aplica pentru a rezolva probleme de calcul în general, iar acestea dau naștere adesea la algoritmi substanțial mai rapizi: : în loc să se caute o soluție optimă, se caută o soluție care este cel mult la un factor distanță de optim. : obținerea unui timp de rulare mediu mai mic, permițând algoritmului să eșueze o oarecare probabilitate redusă. nu este un exemplu bun de algoritm eficient în acest sens anume, deși abordările evoluționiste, cum ar fi algoritmii genetici, ar putea fi. Restricționarea: Prin limitarea structurii de intrare (de exemplu, la grafuri planare), sunt de obicei posibili algoritmi mai rapizi. : de multe ori există algoritmi rapizi dacă anumiți parametri de intrare sunt ficși. Euristică: Un algoritm care funcționează „destul de bine”, în multe cazuri, dar pentru care nu există nici o dovadă că ea este întotdeauna și rapid și mai și produce un rezultat bun. Abordările sunt adesea folosite. Un exemplu de algoritm euristic este un suboptim folosit pentru colorarea grafurilor în faza de de la unele compilatoare, o tehnică numită alocare globală de regiștri cu colorare de graf. Fiecare nod este o variabilă, muchiile înseamnă utilizarea variabilelor în același timp, și culorile indică registrul alocat pentru fiecare variabilă. Deoarece majoritatea mașinilor RISC au un număr destul de mare de regiștri de uz general, chiar și o abordare euristică este destul de eficientă pentru această aplicație.
Completitudinea în raport cu diferite tipuri de reducere În definiția NP-completitudinii dată mai sus, termenul de reducere a fost utilizat în sensul de în timp polinomial.
Un alt tip de reducere este reducerea Turing în timp polinomial. O problemă este Turing-reductibilă în timp polinomial la o problemă dacă, având o subrutină care rezolvă în timp polinomial, s-ar putea scrie un program care apelează această subrutină și rezolvă în timp polinomial. Acest lucru se deosebește de reductibilitatea many-one, care are restricția că programul poate doar apela subrutina o singură dată, iar valoarea returnată de subprogram trebuie să fie valoarea de returnare a programului.
Dacă se definește conceptul analog NP-completitudinii cu reduceri Turing în loc de mai reduceri many-one, mulțimea de probleme rezultată nu va fi mai mică decât cea a problemelor NP-complete; este o întrebare deschisă însă dacă este mai mare.
Un alt tip de reducere adesea folosit pentru a defini NP-completitudinea este , o reducere many-one care poate fi calculată cu o complexitate logaritmică în spațiu. Deoarece fiecare calcul care poate fi făcut în spațiu logaritmic poate fi, de asemenea, efectuat în timp polinomial, rezultă că dacă există o reducere many-one în spațiu logaritmic, atunci există și o reducere many-one în timp polinomial. Acest tip de reducere este mai rafinată decât mai cunoscuta reducere many-one în timp polinomial și permite distingerea mai multor clase, cum ar fi cea a problemelor . Întrebarea dacă în aceste tipuri de reduceri definiția NP-completitudinii se modifică este încă o problemă deschisă. Toate problemele NP-complete cunoscute în prezent sunt problemele NP-complete sub reduceri în spațiu logaritmic. Într-adevăr, problemele NP-complete cunoscute în prezent rămân probleme NP-complete chiar și cu reduceri mult mai slabe. Se știe însă că reducerile definesc o clasă strict mai mică decât reducerile în timp polinomial.
Denumirea