NP-complet

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Diagrama Euler-Venn pentru clasele de complexitate P , NP , NP-Full și NP-hard
Această pagină oferă o descriere tehnică a problemelor NP-complete . Pentru o introducere populară, consultați clasele de complexitate P și NP .

În teoria complexității de calcul , problemele NP-complete sunt cele mai dificile probleme din clasa NP („ probleme nedeterministe în timp polinomial”) în sensul că, dacă s-ar putea găsi un algoritm capabil să rezolve „rapid” (în sensul utilizării polinom de timp ) orice problemă NP-completă, atunci o puteți folosi pentru a rezolva „rapid” orice problemă din NP.

Clasa de complexitate care conține toate problemele NP-complete este adesea denumită NP-C .

Un exemplu de problemă NP-completă este problema sumei parțiale , adică: având în vedere un set finit de numere întregi , determinați dacă există un subset astfel încât suma elementelor sale să fie zero. Este evident că este ușor să verificați rapid dacă un subset este sau nu o soluție la problemă, dar nu se cunoaște nicio metodă pentru a găsi o soluție care este semnificativ mai rapidă decât încercarea tuturor subseturilor posibile, cu excepția celor două care conțin toate numerele concordante (toate negative sau toate pozitive), cele formate dintr-un singur număr negativ și de toate numerele pozitive mai mari în valoare absolută decât numărul negativ și cele formate dintr-un singur număr pozitiv și toate numerele negative mai mari în valoare absolută decât numărul pozitiv.

Definiția formală a completitudinii NP

O problemă este NP complet dacă este în NP și dacă (aparținând și NP),

Asta dacă este cea mai grea problemă din NP.

Cu alte cuvinte, putem spune că un limbaj L este NP-complet dacă următoarele afirmații sunt adevărate:

  1. L este în NP
  2. Pentru fiecare limbă în NP există o reducere polinomială de L 'la L

Aceasta se numește Karp-completeeness, un caz particular de Cook-completeness care definește o problemă NP-complete dacă, dacă este dat un oracol pentru problemă , acesta este un mecanism capabil să răspundă la orice întrebare despre apartenența unui șir la într-o unitate de timp, este posibil să recunoaștem orice limbă din NP în timp polinomial. Definiția completitudinii Cook se dovedește a fi mai generală, astfel încât să includă complementele problemelor NP-complete în clasa problemelor NP-complete.

„Reductibil” înseamnă aici că pentru fiecare problemă L există o reducere polinomială , un algoritm determinist care transformă instanțele lL în instanțe cC , astfel încât răspunsul la c este da dacă și numai dacă răspunsul la l este da. Pentru a demonstra că o problemă NP A este într-adevăr o problemă NP-completă, este suficient să arătăm că o problemă NP-completă cunoscută se reduce la A.

O consecință a acestei definiții este că, dacă am avea un algoritm de timp polinomial pentru C , am putea rezolva toate problemele din NP în timp polinomial.

Această definiție a fost dată de Stephen Cook într-o publicație intitulată „Complexitatea procedurilor de demonstrare a teoremelor” la paginile 151-158 din Proceedings of the 3rd Annual ACM Symposium on Theory of Computing în 1971 , deși termenul NP-complet nu apare. nicăieri în scrierea sa. La acea conferință de informatică, a existat o dezbatere aprinsă între oamenii de știință din domeniul informației cu privire la faptul dacă problemele NP-complete pot fi rezolvate în timp polinomial cu o mașinărie Turing deterministă. John Hopcroft i-a convins pe toți cei prezenți la conferință să lase această întrebare deoparte și să o ia din nou mai târziu, deoarece nimeni nu avea dovezi formale care să dovedească ceea ce spunea. Această întrebare este cunoscută sub numele de dacă problema P = NP .

Nimeni nu a reușit încă să demonstreze dacă problemele NP-complete sunt într-adevăr rezolvabile în timp polinomial, făcând din aceasta una dintre cele mai mari probleme din matematică. Cu toate acestea, există o puternică suspiciune în rândul oamenilor de știință că aceste probleme nu pot fi rezolvate în timp polinomial; conform unui vot informal din 2002 în rândul a 100 de cercetători, pentru 61 dintre ei părea mai probabil ca P ≠ NP, în timp ce doar pentru 9 să fie P = NP . Clay Mathematics Institute din Cambridge, MA oferă recompensa de 1 milion de dolari oricui poate oferi dovezi că P = NP sau P ≠ NP.

La început pare destul de surprinzător faptul că problemele NP-complete ar trebui să existe chiar, dar în celebra teoremă Cook-Levin (dovedită independent de Leonid Levin ), Cook a demonstrat că problema de satisfacție booleană este NP-completă. În 1972, Richard Karp a demonstrat că și alte probleme au fost NP-complete, deci există o clasă de probleme NP-complete (pe lângă problema de satisfacție booleană). Din rezultatul inițial al lui Cook, s-a dovedit că mii de alte probleme sunt NP-complete; multe dintre aceste probleme sunt raportate în Garey and Johnson din 1979 Computers and Intractability: A Guide to NP-Completeness .

O problemă care îndeplinește condiția 2, dar nu neapărat condiția 1 se numește NP-hard . În mod informal, o problemă NP-hard este „cel puțin la fel de dificilă ca” orice problemă NP-completă și poate chiar mai dificilă. De exemplu, alegerea mișcării perfecte în anumite jocuri de masă laterale arbitrare este NP-hard sau chiar strict mai dificilă decât problemele NP-hard.

Exemple de probleme

Un exemplu interesant este problema izomorfismului graficelor , problema teoriei graficelor care constă în determinarea dacă există un izomorfism între două grafice. Două grafice sunt izomorfe dacă unul poate fi transformat în celălalt pur și simplu prin redenumirea vârfurilor sale. Să luăm în considerare aceste două probleme:

  • Izomorfismul graficelor: este graficul G 1 izomorf la graficul G 2 ?
  • Izomorfismul subgrafelor: este graficul G 1 izomorf la un subgraf al graficului G 2 ?

Problema izomorfismului subgrafului este complet NP. Se suspectează că problema izomorfismului grafic nu este nici P, nici NP-complet, deși este evident în NP. Acesta este un exemplu de problemă despre care se crede că este dificil din punct de vedere al calculului, dar despre care se crede că nu este NP-completă.

Cel mai simplu mod de a demonstra că o nouă problemă este NP-completă este să demonstrezi mai întâi că aparține clasei NP și apoi să găsești o reducere de la o problemă cunoscută a fi NP-completă la noua problemă (în formularul său de decizie ).

Iată câteva celebre probleme NP-complete, cu numele în engleză și abrevierea acestuia alături:

Pentru o listă mai completă a problemelor NP-complete , consultați Lista problemelor NP-complete .

Mai jos este prezentată o schiță a unor probleme și reduceri utilizate în mod obișnuit pentru a dovedi completitudinea NP. În diagramă, o săgeată de la o problemă la alta indică direcția reducerii.

Există, de obicei, mici diferențe între problemele P și problemele NP-complete. De exemplu, 3-SAT , o reducere a problemei de satisfacție a formulelor booleene, rămâne NP-completă, în ciuda problemei 2SAT , care este ușor mai puțin strictă atât în ​​P.

Soluții imperfecte

Până acum, toți algoritmii cunoscuți pentru problemele NP-Complete necesită un timp superpolinomial în dimensiunea de intrare. Nu se cunoaște existența unor algoritmi mai rapizi. Prin urmare, pentru a rezolva o problemă NP-Completă non-trivială, sunt utilizate în general următoarele abordări:

  • algoritm de aproximare: un algoritm care găsește rapid o soluție sub-optimă găsită într-o vecinătate (cunoscută) a celei optime.
  • algoritm probabilistic: un algoritm al cărui timp mediu de execuție pentru o anumită distribuție a problemelor este dovedit a fi bun - în mod ideal, unul care atribuie o probabilitate scăzută intrărilor „dificile”.
  • cazuri speciale: un algoritm rapid dacă instanța problemă aparține setului unor cazuri speciale. Parametrizarea complexității poate fi văzută ca o generalizare a acestei abordări.
  • euristic: un algoritm care funcționează „rezonabil de bine” în multe cazuri, dar pentru care nu există nicio dovadă că este întotdeauna rapid și că are performanțe bune.

Un exemplu de algoritm euristic este algoritmul lacom sub-optim O ( n log n ) utilizat pentru problema colorării graficelor în timpul fazei de alocare a registrelor a unor compilatoare. Fiecare vârf este o variabilă, arcurile sunt trasate între variabilele utilizate în același timp, iar culorile indică registrul atribuit fiecărei variabile. Deoarece majoritatea mașinilor RISC au un număr mare de registre generice, o abordare euristică este, de asemenea, eficientă pentru această aplicație.

Completitudine cu diferite tipuri de reducere

În definiția completitudinii NP dată mai sus, termenul „reducere” a fost folosit în sensul său tehnic de reducere mult-la-unu a timpului polinomial .

Un alt tip de reducere este reducerea Turing a timpului polinomial . Având în vedere două probleme X și Y și având în vedere o procedură f care rezolvă Y în timp polinomial, vorbim despre o reducere Turing cu timp polinomial dacă este posibil să scriem un program care apelează f și rezolvă X în timp polinomial. Această definiție a reducibilității este în contrast cu reducibilitatea mai multor persoane. În acesta din urmă, de fapt, programul poate apela procedura o singură dată și valoarea returnată de procedură trebuie să fie valoarea returnată de program.

Dacă am defini un concept analog completității NP folosind reduceri Turing în loc de mai multe la unu, setul de probleme nu ar fi mai mic decât setul celor NP-complete. Nu este încă clar dacă ar fi mai mare. Dacă cele două concepte ar fi aceleași, atunci ar urma că NP = co-NP . Deoarece, prin definiție, setul de probleme NP-complete și complementare sunt egale având în vedere reducibilitatea Turing și întrucât cele două seturi sunt ambele superseturi ale acelorași seturi definite cu reduceri multiple. Prin urmare, dacă ambele definiții ale completitudinii NP sunt egale, există o problemă co-NP-completă (în ambele definiții), cum ar fi complementul problemei de satisfacție booleană, care este, de asemenea, o problemă NP-completă (în ambele definiții). Acest lucru ar implica faptul că NP = co-NP așa cum se vede în dovada articolului co-NP . Deși egalitatea NP și co-NP este o întrebare deschisă, este considerată puțin probabilă și, prin urmare, este la fel de puțin probabil ca cele două definiții ale completitudinii NP să fie echivalente.

Un alt tip de reducere care este adesea utilizat pentru a defini completitudinea NP este reducerea mult-la-unu a spațiului logaritmic . Este o reducere multi-la-unu care poate fi calculată folosind cel mult o cantitate logaritmică de spațiu. Deoarece orice calcul care poate fi făcut într-un spațiu logaritmic poate fi făcut și în timp polinomial , rezultă că, dacă există o reducere de la unu la unu a spațiului logaritmic, există și o reducere de la unu la unu a timpului polinomial . Acest tip de reducere este mai rafinat decât reducerea mai frecventă mult-la-unu a timpului polinomial și permite să distingem mai multe clase de probleme, cum ar fi clasa problemelor P-complete . Dacă în acest tip de reducere modificați definiția completitudinii NP este încă o întrebare deschisă.

Bibliografie

Elemente conexe