Teorema di Cook

Da Wikipedia, l'enciclopedia libera.

Nella teoria della complessità algoritmica, il Teorema di Cook, dimostrato da Stephen Cook nel suo articolo "Complessità delle Procedure di Dimostrazione dei Teoremi" ("The Complexity of Theorem Proving Procedures") del 1971, afferma che il problema di soddisfacibilità booleana è NP-completo.

Indice 1 Teorema di Cook-Levin 2 Definizioni 3 Dimostrazione 4 Conseguenze

[modifica] Teorema di Cook-Levin

Il matematico Russo Levin arrivò per primo alla risoluzione del teorema, ma l'articolo con la dimostrazione venne tradotto in inglese anni dopo la pubblicazione di "Complessità delle Procedure di Dimostrazione dei Teoremi". Perciò questo teorema è noto anche come teorema di Cook-Levin poiché entrambi i matematici arrivarono alla dimostrazione del teorema.

[modifica] Definizioni

Un problema decisionale appartiene ad NP se una Macchina di Turing non deterministica lo può risolvere in tempo polinomiale.

Un problema decisionale è NP-completo se appartiene a NP e se ogni problema appartenente ad NP può essere ridotto ad esso tramite una riduzione molti a uno in tempo polinomiale.

Un'istanza del problema di soddisfacibilità booleana è un'espressione booleana che combina variabili booleane usando degli operatori booleani. Un'espressione è soddisfacibile se c'è almeno un assegnamento di valori di verità alle variabili in modo che l'espressione sia vera.

[modifica] Dimostrazione

Si dimostra che il funzionamento di una Macchina di Turing si può simulare tramite formule booleane in forma normale congiuntiva. Intuitivamente le operazioni di un calcolatore binario (che è Turing Completo o Turing equivalente) possono essere viste come delle formule booleane in forma normale congiuntiva (questo è dovuto all'Architettura dei calcolatori). Si dimostra in maniera banale che ogni formula booleana può essere trasformata in tempo polinomiale in una formula booleana equivalente in forma normale congiuntiva. Ogni problema che può essere risolto tramite una Macchina di Turing può essere tramutato in una formula booleana e quindi il problema di soddisfacibilità booleana è NP-completo.

[modifica] Conseguenze

Una volta dimostrato che ogni problema appartenente a NP può essere ridotto in tempo polinomiale ad una istanza del problema di soddisfacibilità booleana, si deduce che se questo problema potesse essere risolto in tempo polinomiale da una Macchina di Turing deterministica, tutti i problemi in NP potrebbero essere risolti in tempo polinomiale, e quindi la classe di complessità NP sarebbe uguale alla classe di complessità P.