În teoria complexității, cele 21 de probleme NP-complete ale lui Karp sunt o listă de 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  la problema rucsacului. Satisfiabilitatea: problema satisfiabilității booleene pentru formule în (denumită adesea SAT)  (O variantă în care numai restricțiile trebuie să fie îndeplinite, fără optimizare) Problema clicii (echivalentă cu, )

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ă (echivalentă cu 3-SAT) Numărul cromatic (numită și problema colorării grafului)

Problema rucsacului (enunțul lui Karp este mai aproape de problema )

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.  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).

Note

Bibliografie

Categorie:Liste referitoare la matematică Categorie:Probleme NP-complete