NP-completitudine

De la testwiki
Sari la navigare Sari la căutare
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 Format:Ill-wd.

Generalități

Problemele NP-complete sunt în NP, mulțimea tuturor Format:Ill-wd 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 C este NP-completă dacă:

  1. C este în NP, și
  2. Toate problemele din NP sunt Format:Ill-wd la C în timp polinomial.[1]

C este în NP demonstrând că o soluție candidat la C 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.[2]

O consecință a acestei definiții este că, dacă ar exista un algoritm în timp polinomial (pe o Format:Ill-wd, sau pe orice altă Format:Ill-wd) pentru C s-ar putea rezolva toate problemele din NP în timp polinomial.

Context

Conceptul de NP-completitudine a fost introdus în 1971 (a se vedea Format:Ill-wd), deși termenul NP-complet a fost introdus mai târziu. În conferința Format:Ill-wd 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ă. Format:Ill-wd oferă un 1 milion de dolari recompensă pentru oricine demonstrează că P=NP sau că P≠NP.

Format:Ill-wd afirmă că Format:Ill-wd este NP-completă (este disponibilă Format:Ill-wd 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 Format:Ill-wd și Format:Ill-wd din 1979 intitulată Format:Ill-wd.[3] Pentru mai multe detalii, consultați Introducere în Proiectarea și Analiza Algoritmilor de Anany Levitin.

Probleme NP-complete

Unele probleme NP-complete, cu indicarea reducerilor folosite de obicei pentru a le demonstra NP-completitudinea

Un exemplu interesant este cel Format:Ill-wd, problema din teoria grafurilor de a determina dacă există un Format:Ill-wd î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. Format:Colbegin

Format:Colend 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 Format:Ill-wd problema, o restrângere a problemei satisfiabilității booleene, rămâne NP-completă, pe când problema ușor mai restrânsă a Format:Ill-wd este în P (în special, Format:Ill-wd), 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 Format:Ill-wd 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:

  • Format:Ill-wd: în loc să se caute o soluție optimă, se caută o soluție care este cel mult la un factor distanță de optim.
  • Format:Ill-wd: obținerea unui timp de rulare mediu mai mic, permițând algoritmului să eșueze o oarecare probabilitate redusă. Format:Ill-wd 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.
  • Format:Ill-wd: 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 Format:Ill-wd sunt adesea folosite.

Un exemplu de algoritm euristic este un Format:Ill-wd suboptim O(nlog⁡n) folosit pentru colorarea grafurilor în faza de Format:Ill-wd 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 Format:Ill-wd în timp polinomial.

Un alt tip de reducere este reducerea Turing în timp polinomial. O problemă X este Turing-reductibilă în timp polinomial la o problemă Y dacă, având o subrutină care rezolvă Y în timp polinomial, s-ar putea scrie un program care apelează această subrutină și rezolvă X î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 Format:Ill-wd, 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 Format:Ill-wd. Î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.[4] Se știe însă că reducerile Format:Ill-wd definesc o clasă strict mai mică decât reducerile în timp polinomial.[5]

Denumirea

Conform lui Donald Knuth, numele de „NP-complet” a fost popularizat de către Format:Ill-wd, John Hopcroft și Format:Ill-wd în celebrul lor manual „The Design and Analysis of Computer Algorithms”. El declara că aceștia au introdus modificarea într-o Format:Ill-wd a cărții (de la „polinomial-complet”), în conformitate cu rezultatele unui sondaj de opinie a realizat în comunitatea Format:Ill-wd.[6] Alte sugestii făcute în sondaj[7] includeau „herculean”, „formidabil”, „fiert tare”Format:Mdash propus de Steiglitz în onoarea lui Cook, și acronimul „PET” avansat de Shen LinFormat:Mdash cu semnificația „probabil exponențial în timp”; dar, în funcție de direcția în care ar fi mers problema P versus NP, ar putea însemna „demonstrabil (provably) exponențial în timp” sau „anterior (previously) exponențială în timp”.[8]

Greșeli frecvente de înțelegere

Sunt frecvente următoarele greșeli de înțelegere a conceptului.[9]

  • „Problemele NP-complete sunt problemele cele mai dificile cunoscute.” Deoarece problemele NP-complete sunt în NP, timpul lor de funcționare este de cel mult exponențial. Cu toate acestea, sunt unele probleme care se poate demonstra că necesită mai mult timp, de exemplu Format:Ill-wd.
  • „Problemele NP-complete sunt dificile, deoarece există atât de multe soluții diferite.” Pe de o parte, există multe probleme care au un spațiu de soluții la fel de mare, dar care poate fi rezolvate în timp polinomial (de exemplu, arborele minim de acoperire). Pe de altă parte, există probleme NP-probleme cu cel mult o soluție care sunt NP-dure în raport cu reducerea randomizată în timp polinomial (vezi Format:Ill-wd).
  • „Rezolvarea problemelor NP-complete necesită timp exponențial.” În primul rând, acest lucru ar însemna că P ≠ NP, afirmație încă nedemonstrată. Mai mult, unele probleme NP-complete au de fapt algoritmi de funcționare superpolinomiali, dar subexponențiali, de exemplu de complexitate O(2Format:Sqrtn). De exemplu, Format:Ill-wd și Format:Ill-wd sunt NP-complete atunci când sunt limitate la grafuri planare, dar pot fi rezolvate în timp subexponențial pe grafuri planare folosind Format:Ill-wd.[10]
  • „Toate cazurile de probleme NP-complete sunt dificile.”  Adesea, unele cazuri, sau chiar majoritatea cazurilor, pot fi ușor de rezolvat în timp polinomial. Cu toate acestea, în cazul în care P ≠ NP, orice algoritm în timp polinomial trebuie să greșească într-un număr de cazuri mai mult decât polinomial de intrări de o anumită dimensiune.[11]
  • "Dacă P=NP, toate cifrurile criptografice pot fi sparte." Chiar și o problemă în timp polinomial poate fi foarte dificil de rezolvat, în practică, dacă polinomul are grad sau constante sunt suficient de mari. De exemplu, cifrurile cu cheie de lungime fixă, cum ar fi Advanced Encryption Standard, toate pot fi sparte în timp constant (și sunt, prin urmare, deja în P), dar cu tehnologia actuală constanta aceea poate depăși vârsta universului.

Proprietăți

Vizualizarea problemei deciziei ca pe un limbaj formal în unele codificări fixe, mulțimea NPC a tuturor problemelor NP-complete nu este închisă în raport cu:

Nu se știe dacă NPC este închisă în raport cu complementarea, deoarece NPC=Format:Ill-wd dacă și numai dacă NP=Format:Ill-wd, iar această din urmă relație este o Format:Ill-wd.[12]

Referințe

Citări

  1. ↑ Format:Cite book
  2. ↑ Format:Cite book
  3. ↑ Format:Cite book
  4. ↑ Format:Citat revistă
  5. ↑ Format:Citat revistă
  6. ↑ Don Knuth, Tracy Larrabee, and Paul M. Roberts, Mathematical Writing § 25, MAA Notes No. 14, MAA, 1989 (also Stanford Technical Report, 1987).
  7. ↑ Format:Citat revistă
  8. ↑ See the poll, or [1] Format:Webarchive.
  9. ↑ Format:Citat știre
  10. ↑ Format:Harvtxt; Format:Harvtxt; Format:Harvtxt; Format:Harvtxt.
  11. ↑ Format:Citat revistă
  12. ↑ Format:Citation

Surse

Format:Refbegin

Format:Refend

Lectură suplimentară

Format:Refbegin

Format:Refend

Adus de la „https://ro.wiki.beta.math.wmflabs.org/w/index.php?title=NP-completitudine&oldid=1873”