NP-hard

NP-hard (după varianta în engleză, care vine de la „în timp nedeterminist polinomial dificilă) este, în teoria complexității, o proprietate definitorie a unei clase de probleme care sunt, în mod informal, „cel puțin la fel de grele ca cele mai grele probleme din NP”. În română, acestor probleme li se mai spune uneori și NP-dure sau NP-tari. Mai precis, o problemă H este NP-hard, atunci când toate problemele L din NP pot fi reduse în timp polinomial la H, adică: presupunând că o soluție pentru H ia 1 unitate de timp, putem folosi soluția lui H pentru a rezolva L în timp polinomial.^[1]^[2] Ca urmare, găsirea unui algoritm în timp polinomial pentru a rezolva orice problemă NP-hard ar da algoritmi polinomiali pentru toate problemele din NP, ceea ce este puțin probabil, întrucât multe dintre ele sunt considerate dificile.^[3]

O concepție greșită comună este că NP din „NP-hard” vine de la „nepolinomial” când, de fapt, înseamnă „probleme acceptabile Nedeterminist Polinomial”.^[4] Deși se bănuiește că nu există niciun algoritm în timp polinomial pentru probleme NP-hard, acest lucru nu a fost demonstrat.^[5] Mai mult decât atât, clasa P, în care toate problemele pot fi rezolvate în timp polinomial, este conținută în clasa NP.^[6]

Definiție

O problemă de decizie^⁠(d) H este NP-hard, atunci când pentru fiecare problemă L din NP există un o reducere în timp polinomial^⁠(d) a lui L la H^:80 O definiție echivalentă este de a impune ca orice problemă L din NP să poată fi rezolvată în timp polinomial de o mașină oracol^⁠(d) cu un oracol pentru H.^[7] Informal, se poate concepe un algoritm care să poată apela această mașină oracol ca o subrutină pentru rezolvarea H, și rezolvă L în timp polinomial, dacă subrutina de apel se calculează într-un singur pas.

O altă definiție este de a impune ca existența unei reduceri în timp polinomial de la o problemă NP-completă G la H.^:91 Cum orice problemă L din NP se reduce în timp polinomial la G, L se reduce la rândul său, la H în timp polinomial, astfel că această nouă definiție o implică pe cea anterioară. Ea însă nu restricționează clasa NP-hard la probleme de decizie, de exemplu, aceasta include și probleme de căutare^⁠(d), sau probleme de optimizare^⁠(d).

Consecințele

Dacă P ≠ NP, atunci problemele NP-hard nu pot fi rezolvate în timp polinomial.

Unele probleme de optimizare NP-hard pot fi aproximate^⁠(d) în timp polinomial până la un factor de aproximare constant (în special, cele din APX^⁠(d)) sau chiar până la orice raport de aproximare (cele din PTAS^⁠(d) sau FPTAS^⁠(d)).

Exemple

Un exemplu de problemă NP-hard este decizia problemei sumei submulțimii^⁠(d), care este aceasta: fiind dată o mulțime de numere întregi, există vreo submulțime nevidă a ei ale cărei elemente au suma zero? Aceasta este o problemă de decizie^⁠(d), și se întâmplă să fie NP-completă. Un alt exemplu de problemă NP-hard este problema de optimizare de a găsi ciclul de cost minim toate nodurile unui graf ponderat. Aceasta se numește problema comis-voiajorului.^[8]

Există probleme de decizie care sunt NP-hard, dar nu NP-complete, de exemplu, problema opririi^⁠(d). Aceasta este problema care cere „dat fiind un program și un set de date de intrare, va rula acesta la nesfârșit?” Aceasta este o întrebare cu da/nu, deci o problemă de decizie. Este ușor să se demonstreze că problema opririi este NP-hard, dar nu NP-completă. De exemplu, problema satisfiabilității booleene^⁠(d) poate fi redusă la problema opririi prin transformarea acesteia într-o descriere a unei mașini Turing care încearcă toate atribuirile de valori de adevăr și atunci când constată una care satisface formula se oprește, în caz contrar mergând în buclă infinită. Este ușor de văzut și că problema opririi nu este în NP deoarece toate problemele din NP sunt decidabile într-un număr finit de operații, în timp ce problema opririi este, în general, indecidabilă^⁠(d). Există, de asemenea, probleme NP-hard care nu sunt nici NP-complete, nici indecidabile. De exemplu, limbajul de formulelor boolene cuatificate reale^⁠(d) este decidabilă în spațiu polinomial^⁠(d), dar nu în timp nedeterminist polinomial (cu excepția cazului NP = PSPACE^⁠(d)).^[9]

Convenția de denumire NP

Problemele NP-hard nu sunt neapărat elemente ale clasei de complexitate NP. Întrucât noțiunea NP joacă un rol central în complexitatea calculului, este folosită ca bază pentru mai multe clase:

NP: Clasa problemelor de decizie pentru care o anumită soluție poate fi verificată ca soluție în timp polinomial de către o mașină Turing deterministă (sau rezolvabilă de către o mașină Turing nedeterministă în timp polinomial).
NP-hard: Clasa problemelor de decizie care sunt cel puțin la fel de grele ca cele mai grele probleme din NP. Probleme care sunt NP-hard nu trebuie să fie elemente ale NP; într-adevăr, ele pot fi chiar indecidabile.
NP-complete: Clasa problemelor de decizie care conține cele mai grele probleme din NP. Fiecare problemă NP-completă trebuie să fie în NP.
NP-easy^⁠(d): Cel mult la fel de dificile ca NP, dar nu neapărat în NP.
NP-echivalent^⁠(d): Probleme de decizie, care sunt atât NP-hard cât și NP-easy, dar nu neapărat în NP.
NP-intermediar^⁠(d): Dacă P și NP sunt diferite, atunci nu există probleme de decizie în regiunea din NP care se încadrează între problemle P și cele NP-complete. (Dacă P și NP sunt în aceeași clasă, atunci nu există probleme NP-intermediare.)

Referințe

^ Leeuwen, Jan van, ed. (1998). Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier. ISBN 0262720140. OCLC 247934368.
^ Knuth, Donald (1974). „Postscript about NP-hard problems”. ACM SIGACT News. 6 (2): 15–16. doi:10.1145/1008304.1008305. Accesat în 30 ianuarie 2016.
^ Daniel Pierre Bovet; Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. p. 69. ISBN 0-13-915380-2.
^ „P and NP”. Arhivat din original la 19 septembrie 2016. Accesat în 25 septembrie 2016.
^ „Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP”. Accesat în 25 septembrie 2016.
^ „PHYS771 Lecture 6: P, NP, and Friends”. Accesat în 25 septembrie 2016.
^ V. J. Rayward-Smith (1986). A First Course in Computability. Blackwell. p. 159. ISBN 0-632-01307-9. Mai multe valori specificate pentru |autor= și |nume= (ajutor)
^ Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0-471-90413-9 Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor).
^ Mai exact, acest limbaj este PSPACE-complet^⁠(d); vezi de ex. Wegener, Ingo (2005). Complexity Theory: Exploring the Limits of Efficient Algorithms (în engleză). Springer. p. 189. ISBN 9783540210450. .

Michael Garey^⁠(d) și David S. Johnson^⁠(d) (1979). Computers and Intractability^⁠(d). W.H. Freeman. ISBN 0-7167-1045-5. Mai multe valori specificate pentru |autor= și |nume= (ajutor)

[Leeuwen-1] Leeuwen, Jan van, ed. (1998). Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier. ISBN 0262720140. OCLC 247934368.

[2] Knuth, Donald (1974). „Postscript about NP-hard problems”. ACM SIGACT News. 6 (2): 15–16. doi:10.1145/1008304.1008305. Accesat în 30 ianuarie 2016.

[3] Daniel Pierre Bovet; Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. p. 69. ISBN 0-13-915380-2.

[4] „P and NP”. Arhivat din original la 19 septembrie 2016. Accesat în 25 septembrie 2016.

[5] „Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP”. Accesat în 25 septembrie 2016.

[6] „PHYS771 Lecture 6: P, NP, and Friends”. Accesat în 25 septembrie 2016.

[7] V. J. Rayward-Smith (1986). A First Course in Computability. Blackwell. p. 159. ISBN 0-632-01307-9. Mai multe valori specificate pentru |autor= și |nume= (ajutor)

[8] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0-471-90413-9 Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor).

[9] Mai exact, acest limbaj este PSPACE-complet^⁠(d); vezi de ex. Wegener, Ingo (2005). Complexity Theory: Exploring the Limits of Efficient Algorithms (în engleză). Springer. p. 189. ISBN 9783540210450. .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]