P-completezza

Teorema:

$$\mathrm{CIRCUIT\ VALUE} \text{ è } \leq_{\mathrm{LOGSPACE}} \textit{-completo} \text{ per } \mathcal{P}$$

Dimostrazione: sappiamo già che \(\mathrm{CIRCUIT\ VALUE} \in \mathcal{P}\) , quindi prendiamo un qualunque \(I \in \mathcal{P}\) e facciamo vedere che c’è una riduzione \(f \in \mathrm{LOGSPACE}\) che lo trasforma in CIRCUIT VALUE; ovvero \(x \in I \iff f(x)\) è un circuito senza variabili il cui valore è tt.

Sia M una MdT che decide I in \(n^k\) e T la sua tabella di computazione su x. Sia \(\Sigma'\) l’alfabeto di M unito ai nuovi simboli necessari alla costruzione di T: \(\sigma_q \in \Sigma \times Q)\) .

Convertiamo la tabella di computazione di M in un circuito:

1. codifichiamo ogni simbolo in una sequenza di bit \((S_1...S_m) \in \{tt, ff\}^m, m = \lceil \log \#(\Sigma') \rceil\) .
2. la tabella così ottenuta ha \(|x|^k\) righe di stringhe di bit lunghe \(m \times |x|^k\) .
3. rappresentiamo ciascun elemento della tabella con \(S_{i,j,l}, 1 \leq i, j \leq |x|^k, 1 \leq l \leq m\) . Di conseguenza \(\forall i . S_{i,1,1}...S_{i,1,m}\) codifica il simbolo ▷ e \(S_{i,|x|^k,1}...S_{i,|x|^k,m}\) codifica il simbolo # e il resto dipende dai 3 bit della riga sopra, come visto nella tabella di computazione.
4. ci sono m funzioni booleane con 3m ingressi ciascuna che calcolano il bit della stringa successiva.
5. Dato che per ogni funzione booleana esiste un circuito booleano che la calcola, costruiamo il circuito C raggruppando le \(F_1,...,F_m\) funzioni in una unica funzione che restituisce m valori a fronte degli stessi 3m ingressi.

A questo punto, definiamo la riduzione f da I a CIRCUIT VALUE: trasformiamo la tabella di computazione T in un circuito \(C_I\) che è composto da tanti circuiti \(\bar C\) per ogni \(T(i, j)\) . In realtà ne bastano \((|x|^k - 1) \times (|x|^k - 2)\) perché la prima riga e la prima e ultima colonna di T sono fissate. Le uscite di \(\bar C_{i-1,j-1}, \bar C_{i-1,j}, \bar C_{i-1,j+1}\) sono gli ingressi di \(\bar C_{ij}\) . Gli ingressi di \(C_I\) sono quelli di \(T(1,j), T(i,1), T(i, |x|^k)\) che sono determinati da x o sono fissi. I simboli \(\sigma_{SI}, \sigma_{NO}\) vengono codificati con stringhe di soli tt o ff. Poiché abbiamo ipotizzato che la tabella T contiene sempre in posizione \(T(|x|^k, 2)\) , l’uscita di \(C_I\) è una delle uscite di \(\bar C_{|x|^k, 2}\) .

Ora che abbiamo costruito \(C_I\) verifichiamo che sia corretto cioè che \(C_I = f(x) = tt \iff x \in I\) . La dimostrazione procede per induzione sul numero i di passi della computazione:

• caso base \((i = 1)\) : gli ingressi sono le uscite e quindi ok.
• caso induttivo \((i - 1 \implies i)\) : assumo che venga correttamente calcolato il passo i - 1, cioè che \(\forall j. \bar C_{i-1,j}\) ha come uscite \(R_1...R_m \iff T(i - 1, j) = \rho' \in \Sigma'\) è codificato proprio come \(R_1...R_m\) . Il che è verificato per costruzione. Applicando l’ipotesi induttiva la dimostrazione è fatta.

Infine vediamo che lo spazio impiegato dalla riduzione è logaritmico. Per calcolare f dobbiamo costruire e connettere tra loro:

1. le porte di ingresso
2. gli elementi della prima e dell’ultima colonna che sono \(2 \times |x|^k\) circuiti costanti
3. \((|x|^k - 1) \times (|x|^k - 2)\) copie del circuito \(\bar C\) . A ciascuna copia associamo gli appropriati indici, per metterla in relazione con la casella di computazione corrispondente; tali indici sono tutti minori di \(x^k\) e averli rappresenti in binario ci consente di manipolarli in spazio \(\mathcal{O}(\log |x|)\) . □

NP-completezza

Teorema di Cook

Teorema:

$$\mathrm{SAT} \text{ è } \mathcal{NP}\textit{-completo}$$

Dimostrazione: sappiamo già che \(\mathrm{SAT} \in \mathcal{NP}\) , perché abbiamo già visto una procedura che realizza una ricerca esaustiva che lo decide in tempo polinomiale non deterministico.

Poiché \(\mathrm{CIRCUIT\ SAT \leq_{LOGSPACE} SAT}\) , basta dimostrare che \(\mathrm{CIRCUIT\ SAT} \text{ è } \mathcal{NP}\textit{-completo}\) , cioè che \(\forall I \in \mathcal{NP} \implies I \mathrm{\leq_{LOGSPACE} SAT}\) .

Sia allora \(I \in \mathcal{NP}\) . Costruiamo \(f \in \mathrm{LOGSPACE} . x \in I \iff f(x)\) è soddisfacibile. Per ipotesi c’è una MdT non deterministica N che decide I in tempo \(n^k\) . Per semplicità fissiamo il grado di non determinismo a esattamente 2 (ad ogni ci sono sempre 2 scelte possibili). Codifichiamo la prima scelta con un bit ff e la seconda con il bit tt. Una computazione è allora una successione di bit della forma

La definizione di tabella di computazione che abbiamo dato, non contempla il non determinismo, ma possiamo costruirla se fissiamo una successione di scelte B: possiamo costruire T in funzione di N, dell’input x e la successione di scelte B.

Ricordiamo l’osservazione fatta a riguardo delle tabelle di computazione e già sappiamo come sono fatte la prima riga, la prima colonna e l’ultima colonna. Poi riguardando la dimostrazione di P-completezza di CIRCUIT VALUE e procediamo analogamente: il circuito \(\overline{C}_N\) stavolta ha 3m + 1 ingressi e m uscite (T(i, j) dipende da T(i -1, j-1), T(i -1, j), T(i -1 , j + 1), ma anche dalla scelta fatta al passo precedente cioè \(b_{i - 1}\) . Possiamo costruire in LOGSPACE un circuito f(x) che ha come porte di ingresso le scelte non deterministiche codificate nel vettore B e i valore della riga T(1, j) ottenuti dal dato di ingresso x.

Infine f(x) è soddisfacibile se e solo se \(x \in I\) , come abbiamo visto nel teorema di P-completezza di CIRCUIT VALUE. □

Esempi di problemi \(\leq_{\mathrm{LOGSPACE}}\textit{-completi}\text{ per }\mathcal{NP}\) :

• HAM
• CRICCA
• Problema del Commesso Viaggiatore
• Programmazione intera