Dificultate NP

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 12 iulie 2017; verificările necesită 4 modificări .

În teoria complexității computaționale, duritatea NP (duritatea polinomială de timp nedeterministă) este 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 ”. Un exemplu simplu de problemă NP-hard este problema sumei subsetului .

Definiție formală: O problemă de solubilitate este NP-hard dacă orice problemă din NP poate fi redusă în timp polinomial la . O condiție echivalentă necesită ca fiecare problemă din NP să poată fi rezolvată în timp polinomial cu un oracol pentru [1] [2] . Ca o consecință, un algoritm în timp polinomial pentru rezolvarea oricărei probleme NP-hard va produce algoritmi în timp polinomial pentru toate problemele din NP.

Se crede că nu există algoritmi de timp polinomial pentru problemele NP-hard, dar acest lucru nu a fost dovedit (vezi problema P≠NP ) [3] . Mai mult, clasa P , în care toate problemele sunt rezolvate în timp polinomial, este cuprinsă în clasa NP [4] .

Unele probleme de optimizare NP-hard pot fi aproximate polinomial la un factor de aproximare constant (constant) (în special în APX ) sau chiar la orice factor de aproximare (în PTAS sau FPTAS ).

Nume de clase în NP-duritate

Problemele NP-hard nu trebuie să fie elemente ale clasei de complexitate NP. Deoarece clasa NP este o clasă cheie în teoria complexității computaționale , este folosită ca bază pentru următoarele clase:

NP O clasă de probleme de decizie computațională pentru care orice decizie pozitivă dată poate fi verificată ca soluție în timp polinomial de o mașină Turing deterministă (sau rezolvată de o mașină Turing nedeterministă în timp polinomial). NP-hard (NP-hard) O clasă de probleme care nu sunt mai puțin dificile decât cele mai grele probleme din NP. Problemele care sunt NP-hard nu trebuie să fie elemente ale NP; de fapt, astfel de probleme pot fi chiar insolubile. NP-complet (NP-complet) O clasă de probleme de rezolvare care conține cele mai dificile probleme din NP. Fiecare problemă NP-completă trebuie să fie în NP și să se reducă la orice altă problemă NP-completă. NP-intermediar (NP-intermediar) O clasă de probleme de solubilitate intermediară între P și NP-complet, presupunând că clasele P și NP sunt diferite. (Dacă P=NP, atunci nu există NP-intermediare, deoarece fiecare problemă din NP (și P) în acest caz se reduce la NP-complete, care la rândul lor în acest caz se află în NP și, în consecință, în P)

Exemple

Problema sumei submulțimii: Un anumit set de numere întregi are un subset nevid al acestora care se însumează până la zero? Aceasta este o problemă de solubilitate și este NP-complet.

Problema vânzătorului ambulant este o problemă de optimizare a găsirii unei rute ciclice cu cel mai mic cost prin toate nodurile unui grafic ponderat. Aceasta este o problemă NP-hard [5] .

O problemă de oprire este o problemă care este NP-hard, dar nu NP-completă. Sarcina este: „Având în vedere un program și intrarea acestuia, programul se va opri?” Este ușor de demonstrat că problema de oprire este NP-hard, dar nu NP-completă - problema de satisfacție booleană poate fi redusă la o problemă de oprire prin convertirea ei într-o descriere a unei mașini Turing care încearcă toate intrările posibile și atunci când găsește una care satisface formula, se oprește, altfel intră într-o buclă infinită. De asemenea, problema opririi nu este conținută în NP, deoarece toate problemele din NP sunt rezolvabile într-un număr finit de operații, iar problema opririi este indecidabilă .

Există probleme NP-hard care nu sunt nici NP-complete, nici indecidabile . De exemplu, limbajul formulelor booleene cuantificate adevărate este decidabil în spațiu polinomial , dar nu în timp polinomial nedeterminist (dacă NP ≠ PSPACE este adevărat ) [6] .

Aplicații

Problemele NP-hard sunt întâlnite cel mai des în domenii precum:

Note

  1. ↑ Manual de informatică teoretică. - Amsterdam: Elsevier, 1998. - Vol. A, Algoritmi și complexitate. — ISBN 0262720140 .
  2. ↑ Knuth, Donald (1974). Postscript despre problemele NP-hard. Stiri ACM SIGACT . 6 (2): 15-16. DOI : 10.1145/1008304.1008305 .
  3. ↑ Shtetl-Optimized » Blog Archive » Cazul științific pentru P≠NP . www.scottaaronson.com . Preluat: 25 septembrie 2016.
  4. ↑ PHYS771 Cursul 6: P, NP și prietenii . www.scottaaronson.com . Preluat: 25 septembrie 2016.
  5. ↑ Lawler, E.L .; Lenstra, JK ; Rinnooy Kan, AHG & Shmoys, D.B. (1985), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization , John Wiley & Sons, ISBN 0-471-90413-9 , < https://archive.org/details/travelingsalesma00lawl >  .
  6. ↑ Mai precis, acest limbaj este PSPACE-complete ; vezi Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms , Springer, p. 189, ISBN 9783540210450 , < https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA189 >  .