21 problemi NP-completi di Karp

Da Wikipedia, l'enciclopedia libera.

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 intormo al celebre problema P = NP.

I problemi[modifica | modifica sorgente]

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.

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

Note[modifica | modifica sorgente]

  1. ^ Karp 1972
  2. ^ Cook 1971
  3. ^ Zuckerman 1996

Bibliografia[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

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