Nella teoria della complessità computazionale, i 21 problemi NP-completi di Karp sono un insieme di problemi computazionali che si presentano NP-completi. Nel suo saggio del 1972, Reducibility Among Combinatorial Problems ("Riducibilità tra problemi combinatori"),^[1] Richard Karp usò il teorema del 1971 di Stephen Cook secondo cui il problema di soddisfacibilità booleana è NP-completo^[2] (chiamato anche teorema di Cook-Levin) per mostrare che c'è una riduzione molti a uno in tempo polinomiale dal problema di soddisfacibilità booleana a ciascuno dei 21 problemi computazionali di combinatoria e teoria dei grafi, mostrando in tal modo che sono tutti NP-completi. Questa fu una delle prime dimostrazioni che molti problemi computazionali naturali che si presentano in tutta l'informatica sono intrattabili computazionalmente. Questa dimostrazione attirò interesse sullo studio della NP-completezza e sulle ricerche intorno al celebre problema P = NP.

Mentre l'appartenenza del problema SAT o di soddisfacibilità booleana alla classe dei problemi NP-completi fu dimostrata utilizzando meccanismi particolari, le appartenenze dei 21 problemi seguenti furono dimostrate mediante riduzioni polinomiali. Così, il problema SAT si ridusse polinomialmente ai problemi 0-1 INTEGER PROGRAMMING, CLIQUE e 3-SAT, e questi a loro volta si ridussero a vari altri. La lista completa è quella mostrata di seguito. I rientri denotano il fatto che la NP-completezza del problema fu dimostrata mediante la sua riduzione polinomiale nel livello direttamente superiore. Si noti che i nomi dei problemi sono scritti in lettere maiuscole e corrispondono alle abbreviazioni del nome in inglese, com'è usuale; accanto ad essi, tra parentesi, è scritta la traduzione del nome in italiano.

• SAT (Problema di soddisfacibilità booleana, per formule in forma normale congiuntiva)
  • 0-1 INTEGER PROGRAMMING (Problema della programmazione lineare intera)
  • CLIQUE (Problema della cricca, si veda anche Problema dell'insieme indipendente)
    • SET PACKING (Problema dell'impacchettamento degli insiemi)
    • VERTEX COVER (Problema di copertura dei vertici)
      • SET COVERING (Problema di copertura degli insiemi)
      • FEEDBACK NODE SET (o Feedback vertex set) (Problema dell'insieme dei vertici in retroazione)
      • FEEDBACK ARC SET (Problema dell'insieme degli archi in retroazione)
      • DIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano diretto)
        • UNDIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano non diretto)
  • 3-SAT (Problema di soddisfacibilità booleana con 3 letterali per clausola)
    • CHROMATIC NUMBER (Problema di colorazione dei grafi)
      • CLIQUE COVER (Problema di copertura delle cricche)
      • EXACT COVER (Problema della copertura esatta)
        • HITTING SET (Problema dell'insieme intersecante)
        • STEINER TREE (Albero di Steiner)
        • 3-DIMENSIONAL MATCHING (Problema dell'accoppiamento tridimensionale)
        • KNAPSACK (Problema dello zaino)
          • JOB SEQUENCING (Problema delle sequenze di lavoro)
          • PARTITION (Problema della partizione)
            • MAX-CUT (Problema del taglio massimo)

Con il passare del tempo si scoprì che molti di questi problemi potevano essere risolti in modo efficiente se il loro enunciato era limitato a certi casi particolari, o potevano essere risolti approssimativamente entro una certa percentuale del risultato ottimale. Tuttavia, David Zuckerman dimostrò nel 1996 che ognuno di questi 21 problemi ha una versione limitata di ottimizzazione che è impossibile approssimare entro qualsiasi fattore costante a meno che P = NP, dimostrando che l'approccio della riduzione, proposto da Karp, generalizza a un tipo specifico di riduzione per approssimazione.^[3] Si noti che questa può essere diversa dalle versioni normali di ottimizzazione dei problemi, che possono avere algoritmi di approssimazione (come nel caso del taglio massimo).

• Stephen Cook, The Complexity of Theorem Proving Procedures, in Proceedings of the third annual ACM symposium on Theory of computing, 1971, pp. 151–158.
• Richard M. Karp, Reducibility Among Combinatorial Problems (PDF), in R.E. Miller e J.W. Thatcher (a cura di), Complexity of Computer Computations, New York, Plenum, 1972, pp. 85–103.
• David Zuckerman, On Unapproximable Versions of NP-Complete Problems, in SIAM Journal on Computing, vol. 25, n. 6, 1996, pp. 1293–1304, DOI:10.1137/S0097539794266407.

• NP-completo

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica