21 problemi NP-completi di Karp

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"), Richard Karp usò il teorema del 1971 di Stephen Cook secondo cui il problema di soddisfacibilità booleana è NP-completo (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.

I problemi

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

Bibliografia

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

Voci correlate

• NP-completo