Cele 21 de probleme NP-complete ale lui Karp

În teoria complexității, cele 21 de probleme NP-complete ale lui Karp sunt o listă de probleme de calcul⁠(d) NP-complete. În articolul publicat de el în 1972 și intitulat "Reducibility Among Combinatorial Problems" (în traducere liberă, „Reductibilitatea între problemele combinatorice”), [1] Richard Karp a folosit teorema lui Stephen Cook din 1971 conform căreia problema satisfiabilității booleene este NP-completă[2] (numită și teorema Cook-Levin) pentru a arăta că există o reducere neinjectivă în timp polinomial de la problema sa satisfiabilității booleene la oricare dintr-o listă de 21 de probleme de calcul de combinatorică și teoria grafurilor, demonstrând astfel că toate acestea sunt NP-complete. Aceasta a fost una dintre primele demonstrații că multe probleme naturale de calcul care apar în diverse locuri în informatică sunt intractabile computațional, și a atras atenția asupra studiului NP-completitudinii și problemei P versus NP.

Problemele

modificare

Cele 21 de probleme ale lui Karp sunt enumerate mai jos, multe cu numele lor inițiale. Imbricarea listei indică direcția de reducere folosită. De exemplu, problema rucsacului a fost demonstrată a fi NP-completă prin reducerea problemei acoperirii exacte⁠(d) la problema rucsacului.

Cu trecerea timpului, s-a descoperit că multe dintre probleme pot fi rezolvate eficient dacă se limitează la cazuri speciale, sau pot fi rezolvate aproximativ cu eroare de un procent fix față de rezultatul optim. David Zuckerman⁠(d) a arătat însă în 1996 că toate aceste 21 de probleme au o versiune optimizată cu constrângeri care este imposibil de aproximat cu orice factor constant dacă P ≠ NP, arătând că abordarea lui Karp asupra reducerii se generalizează la un anumit tip de reducere a aproximabilității.[3] Acestea pot fi însă diferite de versiunile optimizate standard ale problemelor, care pot avea algoritmi de aproximare (ca în cazul tăierii maxime).

Bibliografie

modificare
  • Stephen Cook (). „The Complexity of Theorem Proving Procedures”. Proceedings of the third annual ACM symposium on Theory of computing. pp. 151–158.  Mai multe valori specificate pentru |autor= și |nume= (ajutor)
  • Richard M. Karp (). „Reducibility Among Combinatorial Problems” (PDF). În R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.  Mai multe valori specificate pentru |autor= și |nume= (ajutor)
  • Zuckerman, David (). „On Unapproximable Versions of NP-Complete Problems”. SIAM Journal on Computing. 25 (6): 1293–1304. doi:10.1137/S0097539794266407.  Mai multe valori specificate pentru |DOI= și |doi= (ajutor) [1] Arhivat în , la Wayback Machine.