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”), Richard Karp a folosit teorema lui Stephen Cook din 1971 conform căreia problema satisfiabilității booleene este NP-completă (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

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.

• Satisfiabilitatea^⁠(d): problema satisfiabilității booleene pentru formule în formă normală conjunctivă^⁠(d) (denumită adesea SAT)
  • Programarea întreagă 0-1^⁠(d) (O variantă în care numai restricțiile trebuie să fie îndeplinite, fără optimizare)
  • Problema clicii (echivalentă cu, problema mulțimii independente^⁠(d))
    • set packing^⁠(d)
    • Acoperirea cu noduri^⁠(d)
      • Acoperirea cu mulțimi^⁠(d)
      • Mulțimea nodurilor de reacție^⁠(d)
      • Mulțimea arcelor de reacție^⁠(d)
      • Circuitul Hamilton orientat (numele dat de Karp, acum denumită ciclul hamiltonian orientat)
        • Circuitul Hamilton neorientat (numele dat de Karp, acum denumită ciclul hamiltonian neorientat)
  • Satisfiabilitatea cu cel mult 3 literali pe clauză^⁠(d) (echivalentă cu 3-SAT)
    • Numărul cromatic (numită și problema colorării grafului)
      • Acoperirea cu clici^⁠(d)
      • Acoperirea exactă^⁠(d)
        • set cover problem^⁠(d)
        • Arborele Steiner^⁠(d)
        • Cuplajul tridimensional^⁠(d)
        • Problema rucsacului (enunțul lui Karp este mai aproape de problema sumei submulțimilor^⁠(d))
          • Secvențierea joburilor^⁠(d)
          • Partiția^⁠(d)
            • Tăierea Max^⁠(d)

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. Acestea pot fi însă diferite de versiunile optimizate standard ale problemelor, care pot avea algoritmi de aproximare (ca în cazul tăierii maxime).

Bibliografie

• Stephen Cook (1971). „The Complexity of Theorem Proving Procedures”. Proceedings of the third annual ACM symposium on Theory of computing. pp. 151–158. 
• Richard M. Karp (1972). „Reducibility Among Combinatorial Problems” (PDF). În R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.  Mentenanță CS1: Text în plus: lista editorilor (link)
• Zuckerman, David (1996). „On Unapproximable Versions of NP-Complete Problems”. SIAM Journal on Computing. 25 (6): 1293–1304. doi:10.1137/S0097539794266407.  [1] Arhivat în 22 februarie 2006, la Wayback Machine.