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