NP-dificil

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

În teoria complexității , NP-hard sau probleme NP-dure (în engleză NP-tare, de la nondetermistic problema polinomial-greu) sunt o clasă de probleme care pot fi definite în mod informal, clasa de probleme , cel puțin la fel de dificil ca cel mai dificil probleme de clasele de complexitate P și NP . Mai formal, o problemă este NP-dificil dacă și numai dacă există o problemă NP este reductibil polinomial la , sau astfel încât . Cu alte cuvinte, trebuie să poată fi rezolvat în timp polinomial de o mașină Turing echipată cu un oracol pentru . [1] Din această definiție rezultă că problemele NP-dificile nu sunt mai puțin dificile decât problemele NP-complete , care la rândul lor sunt prin definiție cele mai dificile dintre clasele P / NP.

Categoria problemelor dificile NP, spre deosebire de clasele P, NP și NP-complete, nu este limitată prin definiție doar la problemele de decizie ; de fapt, există și probleme de optimizare și alte tipuri.

Clasa problemelor NP-dificile are o mare relevanță teoretică și practică. În practică, a demonstra că o problemă de calcul este echivalentă cu o problemă notoriu dificilă de NP înseamnă a demonstra că este practic imposibil [2] să se găsească o modalitate eficientă de a o rezolva, ceea ce are multe implicații în informatică . Din punct de vedere teoretic, studiul problemelor dificile NP este un element esențial al cercetării asupra unora dintre principalele probleme deschise de complexitate.

Observații

  • Deoarece problemele NP-complete sunt reductibile una la alta în timp polinomial și toate problemele din NP sunt reductibile la probleme NP-complete în timp polinomial, rezultă că, având în vedere orice problemă NP-dificilă , toate problemele din NP pot fi reduse în timp polinomial la aceasta. În consecință, dacă s-ar găsi o soluție în timp polinomial la orice problemă dificilă de NP, aceasta ar putea fi utilizată pentru a rezolva toate problemele din NP. Acest lucru ar arăta că . Deși nu s-a găsit încă nicio dovadă, comunitatea științifică crede în general că P și NP nu coincid. [3]
  • Mai exact: dacă , atunci problemele NP-hard nu au o soluție polinomială. Dimpotrivă, dacă ar fi adevărat că , solvabilitatea polinomială a problemelor dificile NP nu ar fi dedusă din aceasta.
  • Dacă o problemă de optimizare H are o versiune L, unde L este NP-complet , atunci H este NP-dificil;
  • Dacă H aparține NP , atunci H este, de asemenea, NP-complet, deoarece în acest caz reducerea polinomială respectă criteriile unei reduceri între problemele NP-complete.

Exemple

O problemă tipică NP-hard, calculul celei mai scurte căi complete dintr-un grafic

Un exemplu de problemă NP-dificilă este problema deciziei cunoscută sub numele de problema sumelor parțiale sau „SUBSET-SUM” și care corespunde întrebării: dat un set de numere întregi, există cel puțin un subset al acesteia care are zero algebric suma ? O celebră problemă de optimizare NP-dificilă, care are și o valoare practică foarte puternică, este aceea de a găsi calea hamiltoniană care unește două puncte pe un grafic.

Există probleme de luare a deciziilor care sunt NP-dificile, dar nu NP-complete, această clasă include problemele care se află în EXPTIME, adică toate acele probleme de luare a deciziilor care pot fi rezolvate de o mașinărie Turing deterministă în timpul O ( ), unde f (n) este o funcție polinomială. O problemă este NP-hard dacă toate problemele din NP sunt polinomial reductibile la aceasta. Un exemplu de problemă NP-hard este problema cu formula booleană satisfăcătoare SAT ). Se poate demonstra că problemele NP-complete sunt polinomial reductibile la această problemă (o dovadă este cunoscută de exemplu pentru 3sat ). Cu toate acestea, există și exemple de probleme care sunt NP-dificile, decizibile, dar nu NP-complete; un exemplu este problema recunoașterii limbajului TQBF ( True Quantified Boolean Formulas ).

Definiție alternativă

O definiție alternativă a NP-hard care este adesea utilizată restricționează NP-Hard la problemele de decizie și, prin urmare, utilizează reducerea polinomială în locul reducerii Turing. Astfel, formal un limbaj L este NP-hard dacă .

Convenții de nomenclatură familială NP

Nomenclatura problemelor NP este confuză: problemele dificile NP nu sunt în NP, în ciuda faptului că au fost etichetate cu acest nume. În ciuda acestei contradicții verbale, acest nume este acum în uz comun. Pe de altă parte, sistemul de nomenclatură NP are o semnificație mai profundă, care interesează clasa sa de complexitate generică, numită și NP .

  • NP-complete - identifică problemele care sunt complete în NP.
  • NP-dificil - identifică problemele care sunt cel puțin la fel de complexe ca cele din NP (dar nu aparțin în mod necesar NP);
  • NP-simplu - identifică problemele care sunt cel mai bine la fel de complexe ca cele din NP (dar nu aparțin neapărat NP);
  • NP-echivalente - identifică problemele care sunt exact echivalente cu NP, (dar nu aparțin neapărat lui NP);

Notă

  1. ^ Adică echipat cu un mecanism ipotetic care îi permite să aibă instantaneu soluția problemei . Dacă aveți soluția de „eliberează” soluția de este "ieftin" (vezi definiția timpului polinomial ), rezultă că nu poate fi semnificativ mai simplu decât .
  2. ^ Una dintre problemele deschise ale teoriei complexității este dacă este posibil să se găsească un algoritm eficient (formal: în timp polinomial) pentru problemele NP-complete. În consecință, teoretic nu este imposibil să se găsească un algoritm eficient pentru a rezolva o problemă dificilă de NP. Cu toate acestea, niciun astfel de algoritm nu a fost identificat vreodată de comunitatea științifică și, în general (chiar și în absența unei dovezi matematice) este înclinat să creadă că un astfel de rezultat este imposibil.
  3. ^ Întrebarea „P = NP?” aparține așa-numitelor probleme ale mileniului . Deși tendința generală a comunității științifice este de a crede că răspunsul este „nu”, ipoteza opusă a fost formulată și de ilustri matematicieni precum Kurt Gödel .

Bibliografie

linkuri externe