Teorema di Cook-Levin

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Teorema di Cook)

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")[1] del 1971, afferma che il problema di soddisfacibilità booleana è NP-completo. Il matematico russo Leonid Levin arrivò per primo alla risoluzione del teorema[2], 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.

Definizioni[modifica | modifica wikitesto]

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.

Dimostrazione[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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

Questa macchina effettua nondeterministicamente 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[modifica | modifica wikitesto]

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 possibile all'interno di questo ramo sono al più nk configurazioni. Quindi è possibile creare una tabella avente nk righe ed nk 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 determinare condizioni di questa tabella:

  • ad ogni cella è associato una 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} \and \phi_{start} \and \phi_{move} \and \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 una ed un solo simbolo[modifica | modifica wikitesto]

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 una 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) \and \left( \bigwedge_{s,t \in C; s \neq t} (\overline{x_{i,j,s}}\or \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[modifica | modifica wikitesto]

La formula che lo verifica è:

\phi_{start} = x_{1,1,\# } \and x_{1,2,q_0} \and x_{1,2,w_1} \and x_{1,3,w_2} \and \ldots \and x_{1,n+2,w_n} \and x_{1,n+3,\_ } \and \ldots \and x_{1,n^k,\# }

Ogni transizione da una riga alla riga successiva è valida[modifica | modifica wikitesto]

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.

Almeno una riga della tabella rappresenta uno stato di accettazione[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.


Note[modifica | modifica wikitesto]

  1. ^ Stephen Cook, The complexity of theorem-proving procedures in STOC '71 Proceedings of the third annual ACM symposium on Theory of computing, New York, ACM, 1971, pp. 151-158, DOI:10.1145/800157.805047.
  2. ^ Leonid Levin, Universal search problems (in russo: Универсальные задачи перебора?, Universal'nye perebornye zadachi) in Problems of Information Transmission (in russo: Проблемы передачи информации?, Problemy Peredachi Informatsii), vol. 9, nº 3, 1973, pp. 115–116. (pdf)

Bibliografia[modifica | modifica wikitesto]

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