Teorema di Cook-Levin

Nella teoria della complessità algoritmica, il teorema di Cook-Levin, 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. Il matematico sovietico Leonid Levin arrivò per primo alla dimostrazione 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 indipendentemente alla dimostrazione del teorema.

Definizioni

Un problema decisionale appartiene ad NP se una macchina di Turing non deterministica può calcolare la soluzione in tempo polinomiale.

Un problema decisionale è NP-completo se appartiene a NP e se ogni problema appartenente ad NP può essere ridotto ad esso 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 tale che l'espressione sia vera.

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.

SAT appartiene ad NP

SAT appartiene ad NP, perché esiste una macchina di Turing non deterministica che può decidere tutti i problemi in SAT.

Questa macchina effettua in modo non deterministico tutte le assegnazioni possibili alla formula booleana, se almeno una delle assegnazioni soddisfa la formula booleana, la macchina accetta.

Ogni linguaggio in NP è riducibile a SAT in tempo polinomiale

Viene qui riportata la dimostrazione che si trova sul libro di Michael Sipser.

Usiamo una tabella per codificare tutti gli stati di un ramo di una computazione di una macchina non deterministica. Quindi l'alfabeto dei simboli che compaiono nella tabella è:

$C=Q\cup \Gamma \cup \{\#\}$

Visto che ogni ramo di computazione può avere al più tempo polinomiale, sappiamo che gli stati possibili all'interno di questo ramo sono al più n^k configurazioni. Quindi è possibile creare una tabella avente n^k righe ed n^k colonne, di cui ogni riga rappresenta una configurazione del ramo di computazione.

Ogni riga di questa tabella contiene il contenuto del nastro della macchina di Turing e lo stato corrente, messo prima del simbolo su cui la macchina punta attualmente. Inoltre, il simbolo # rappresenta l'inizio e la fine di ogni stringa ed il simbolo _ rappresenta una cella vuota. Ad esempio, una configurazione iniziale conterrà i simboli:

#, q0, w0, w1, ... , wn, _ , ... , _ , #

E se la testina dovesse spostarsi in avanti, si avrebbe la stringa:

#, w0, q0, w1, ... , wn, _ , ... , _ , #

È possibile creare un insieme di formule booleane che verifichino determinate condizioni di questa tabella:

• ad ogni cella è associato un ed un solo simbolo;
• la prima riga della tabella rappresenta la configurazione iniziale;
• ogni transizione da una riga alla riga successiva è valida;
• almeno una riga della tabella rappresenta uno stato di accettazione.

La formula finale sarà la congiunzione di queste quattro formule:

$\phi =\phi _{cell}\land \phi _{start}\land \phi _{move}\land \phi _{accept}$

Detto questo, bisogna dimostrare due cose:

• è effettivamente possibile generare una formula booleana di lunghezza polinomiale dalla congiunzione delle formule di cui sopra;
• una assegnazione di tale formula rappresenta un ramo di computazione che accetti

Ad ogni cella è associato uno ed un solo simbolo

Introduciamo le variabili booleane $x_{i,j,s}$ che hanno valore "vero" se la cella nella riga i e nella colonna j contiene il simbolo s, "falso" altrimenti.

La formula che verifica che ad ogni cella sia associato uno ed un solo simbolo è:

$\phi _{cell}=\bigwedge _{1\leq i,j\leq n^{k}}\left[\left(\bigvee _{s\in C}x_{i,j,s}\right)\land \left(\bigwedge _{s,t\in C;s\neq t}({\overline {x_{i,j,s}}}\lor {\overline {x_{i,j,t}}})\right)\right]$

La formula ci sta dicendo che per ogni cella, corrispondente alla riga i ed alla colonna j, dobbiamo verificare due cose:

• nella cella c'è almeno un simbolo;
• in nessuna cella c'è più di un simbolo.

Questo è un controllo più che altro sintattico sul contenuto della tabella. In questa formula non viene fatta alcuna verifica sul reale significato dei simboli presenti.

La prima riga della tabella rappresenta la configurazione iniziale

La formula che lo verifica è:

$\phi _{start}=x_{1,1,\#}\land x_{1,2,q_{0}}\land x_{1,3,w_{1}}\land x_{1,4,w_{2}}\land \ldots \land x_{1,n+2,w_{n}}\land x_{1,n+3,\_}\land \ldots \land x_{1,n^{k}-1,\_}\land x_{1,n^{k},\#}$

Ogni transizione da una riga alla riga successiva è valida

Questa è la condizione più difficile da verificare in assoluto. Per questo motivo verrà fornito un abbozzo di dimostrazione.

È possibile verificare la correttezza delle righe analizzando solamente delle "finestre" di due righe e tre colonne. Di ognuna di queste finestre si potrà dire se è giusta o sbagliata guardando alla funzione di transizione della macchina di Turing che si sta simulando e a dei controlli formali.

Una finestra di due righe e tre colonne può essere non corretta per i seguenti motivi:

• un simbolo che cambia da una riga ad un'altra senza che la testina sia puntata sulla cella in cui il simbolo si trova;
• una riga contiene due stati della macchina di Turing;
• i simboli scritti e gli spostamenti a destra o sinistra non rientrano nella funzione di transizione della macchina di Turing.

Cioè:

$\phi _{move}=\bigwedge _{1\leq i<n^{k},1<j<n^{k}}({\text{la finestra (i, j) è lecita}})$

La finestra (i, j) è la finestra di due righe e tre colonne che ha la cella in alto al centro in posizione (i, j).

Almeno una riga della tabella rappresenta uno stato di accettazione

Si tratta di verificare che almeno una cella della tabella contiene uno stato di accettazione.

$\phi _{accept}=\bigvee _{1\leq i,j\leq n^{k}}x_{i,j,q_{accept}}$

Abbiamo detto che la tabella rappresenta un ramo di una computazione di una macchina di Turing non deterministica, dobbiamo accertarci però che si tratti di un ramo di computazione che termina con l'accettazione.

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.

Bibliografia

• (EN) Sanjeev Arora, Bazra Barak, Computational complexity: a modern approach, 2009, Cambridge University Press, ISBN 978-0-521-42426-4.
• Michael Sipser, Introduction to the Theory Of Computation, Terza Edizione, Cengage Learning, 2013, ISBN 978-1-133-18779-0.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su teorema di Cook