Oggi approfondiamo la classe di complessità LOGSPACE e scopriamo che questa classe ci consente di classificare le famigerate classi di complessità P e NP.
Per classificare P e NP tratteremo alcuni problemi e dimostreremo la loro appartenenza all’una o l’altra classe. Domani dimostreremo anche che alcuni di questi problemi sono P-completi o NP-completi secondo LOGSPACE.
Più precisamente considereremo la relazione di riduzione
\(\leq_{\mathrm{LOGSPACE}}\)
, cioè la relazione che impiega algoritmi che
appartengono alla classe di complessità
\(\mathrm{LOGSPACE} = \bigcup_{k \geq 1} \mathrm{SPACE}(k \times \log n)\)
e vedremo che la relazione \(\leq_{\mathrm{LOGSPACE}}\)
classifica
\(\mathcal{P}\)
e \(\mathcal{NP}\)
.
Successivamente cerchermeo i problemi H che siano
\(\mathcal{P}\text{-completi}\)
, cioè tali per cui ogni problema
\(I \in \mathcal{P}\)
si riduce ad H (cioè H è arduo) e inoltre
\(H \in \mathcal{P}\)
(e quindi H è completo).
Procederemo analogamente per \(\mathcal{NP}\)
.
I problemi completi caratterizzano davvero una classe di complessità, perchè ne esprimono la struttura profonda e l’essenza e la difficoltà dei suoi problemi. Di conseguenza attraverso un problema completo si esprime anche il potere espressivo di una classe.
Ricordiamo questo frammento di gerarchia tra le classi di complessità:
e ricordiamo anche che \(\mathrm{LOGSPACE \subsetneq PSPACE}\)
.
Di conseguenza almeno una delle inclusioni
deve essere stretta. A tutt’oggi però non sappiamo quale essa sia, e non ci
aiuta sapere anche che \(\mathcal{P} \subsetneq \mathrm{EXP}\)
e
\(\mathcal{NP} \subseteq \mathrm{EXP}\)
.
Il problema piú interessante in questo momento è risolvere
\(\mathcal{P} \stackrel{?}{=} \mathcal{NP}\)
, che, oltre che estremamente
affascinante si è rivelato resistentissimo, tanto che non si sa neppure se sia
dimostrabile.
Se facessimo vedere che un problema \(\mathcal{NP}\text{-completo}\)
è
risolto da un algoritmo che richiede tempo polinomialmente deterministico, o che
si riduce ad un problema \(\mathcal{P}\text{-completo}\)
, avremmo tutto
d’un chiocco dimostrato l’eguaglianza tra la classe dei problemi trattabili e dei
problemi che divengono tali solo grazie al non determinismo. Cioè esisterebbe un
modo computazionalmente accettabile di realizzare il meccanismo del non
determinismo.
Tuttavia si tende a pensare che l’uguaglianza non valga perché ci sono tutta una serie di indizi che puntano in questa direzione.
Problemi trattabili e problemi intrattabili
Discutiamo la fondatezza della tesi di Cook-Karp, che afferma che i problemi in
\(\mathcal{P}\)
sono trattabili, mentre quelli in
\(\mathcal{NP}\)
sono intrattabili.
Chiariamo subito alcune proprietà dell’insieme P.
Proprietà: \(\mathcal{P}\)
è chiusa rispetto alla composizione polinomiale sinistra, cioè se per tutti i polinomi \(p, f \in \mathcal{P} \implies p \circ f \in \mathcal{P}\)
.
Dimostrazione: si può sempre trovare un algoritmo T di complessità p che, dato
un problema I, trasforma una sua procedura di decisione M in una equivalente P.
Se M ha complessità polinomiale f, allora P avrà complessità
\(p \circ f\)
, che è ancora un polinomio.
□
Proprietà: \(\mathcal{P}\)
.
Dimostrazione: dato un problema I, posso ridurlo, per mezzo di un algoritmo M
che ha come complessità un polinomio p, in \(I' = M(I)\)
e decido I’; se
\(I' \in \mathcal{P}\)
, cioè I’ è deciso in tempo deterministico
polinomiale f, anche \(I \in \mathcal{P}\)
perché è deciso in tempo
deterministico \(f \circ p\)
, che è ancora un polinomio.
□
Vediamo ora una proprietà di LOGSPACE.
Proprietà: la composizione di due macchine che operano in spazio logaritmico è ancora una macchina in \(\mathrm{LOGSPACE}\)
Dimostrazione: lancio la seconda macchina e appena questa richiede un carattere
in ingresso, lo facciamo calcolare dalla prima; questo metodo richiede molto
tempo per i “context switch”, e una casella per memorizzare temporaneamente il
carattere generato dalla prima macchina, ma non ci interessa il tempo: consumando
una sola casella in più restiamo nella classe \(\mathrm{LOGSPACE}\)
.
Di conseguenza \(\mathrm{LOGSPACE}\)
è chiusa per composizione.
Definizione: un problema \(I\)
si riduce efficientemente a \(I' (I \leq_{\mathrm{LOGSPACE}} I')\)
se esiste un algoritmo \(f \in \mathrm{LOGSPACE}\)
tale che:
$$x \in I \iff f(x) \in I'$$
LOGSPACE classifica P e NP
La classe di funzioni in \(\mathrm{LOGSPACE}\)
induce una relazione di
riduzione che classifica \(\mathrm{LOGSPACE}\text{ e }\mathcal{D}\)
, dove
D è una delle classi che abbiamo introdotto. In altre trattazioni della materia
si usa la relazione di riduzione \(\mathcal{P}\)
, il che è equivalente
in quanto le riduzioni LOGSPACE sono più “facili” di quelle polinomiali.
Teorema: siano \(\mathcal{D, E} \in \{\mathcal{P, NP}, \mathrm{EXP, PSPACE, NPSPACE}\} \wedge \mathcal{D} \subseteq \mathcal{E}\)
- \(\leq_{\mathrm{LOGSPACE}} \text{ classifica }\{\mathrm{LOGSPACE}\} \text{ ed } \mathcal{E}\)
- \(\leq_{\mathrm{LOGSPACE}} \text{ e a maggior ragione } \leq_{\mathcal{P}} \text{ classificano } \mathcal{D} \text{ ed } \mathcal{E}\)
Dimostrazione: il primo enunciato è vero perché le ipotesi del lemma sulle relazioni di riduzioni sono soddisfatte:
- \(\mathrm{LOGSPACE}\)
- \(\mathrm{LOGSPACE}\)
- è vero che \(f \in \mathrm{LOGSPACE}, B \in \mathrm{LOGSPACE}
\implies \{x | f(x) \in B\} \in \mathrm{LOGSPACE}\)
, cioè se prendo una macchina in \(\mathrm{LOGSPACE}\)
gli basta uno spazio logaritmico (0 celle per accettare sempre?). Inoltre la funzione caratteristica è \(f \circ \chi_I\)
che essendo composizione di funzioni LOGSPACE è anche’essa LOGSPACE.
- è vero che \(f \in \mathrm{LOGSPACE}, B \in \mathcal{E} \implies
\{x | f(x) \in B\} \in \mathcal{E}\)
, perché la macchina che calcola f usa meno o lo stesso spazio della macchina che calcola la funzione caratteristica analogamente a quanto visto sopra.
Il secondo enunciato è vero perché:
- \(\mathrm{LOGSPACE}\text{ e }\mathcal{P}\)
hanno identità
- \(\mathrm{LOGSPACE}\text{ e }\mathcal{P}\)
- è vero che \(f \in \mathrm{LOGSPACE}\text{ oppure }\mathcal{P},
B \in \mathcal{D} \implies \{x | f(x) \in B\} \in \mathcal{D}\)
- è vero che \(f \in \mathrm{LOGSPACE}\text{ oppure }\mathcal{P},
B \in \mathcal{E} \implies \{x | f(x) \in B\} \in \mathcal{E}\)
Problema SAT
Il problema SAT o di soddisfacibilità booleana consiste nel decidere se, data una
espressione booleana B esiste un assegnamento \(\mathcal{V . V} \models B\)
,
cioè stabilire se B è soddisfacibile.
SAT appartiene a \(\mathcal{NP}\)
perché basta usare una macchina non
deterministica che esamina tutti i possibili assegnamenti e si arresta in tempo
polinomiale.
La certificazione, ovvero il controllo che un assegnamento proposto sia effettivamente una soluzione richiede un tempo polinomiale: Basta imporre che le formule siano scritte in forma normale congiuntiva e calcolare |x| volte un and logico per vedere se l’assegnamento soddisfa la formula.
Problema HAM
Decidere se in grafo orientato c’è un cammino hamiltoniano, cioè che tocca tutti i nodi una e una sola volta.
HAM si riduce in spazio logaritmico a SAT, cioè SAT è un problema almeno tanto difficile quanto lo è HAM.
Proprietà:
$$HAM \leq_{\mathrm{LOGSPACE}} SAT$$
Dimostrazione: omessa. Va costruita una riduzione che dato un grafo lo riconduce ad un problema di soddisfacibilità e poi va dimostrato che la riduzione sta in LOGSPACE.
Problema CRICCA
Decidere se in un grafo non orientato \(G = (N,A),\exists\> C \subseteq N\)
,
detto cricca, tale che:
In altre parole “basta” trovare un sotto-grafo completo.
SAT si può ridurre in spazio logaritmico a CRICCA, cioè CRICCA è un problema almeno tanto difficile quanto lo è SAT.
Proprietà:
$$SAT \leq_{\mathrm{LOGSPACE}} CRICCA$$
Dimostrazione: data un’espressione booleana
\(B = \bigwedge_{1 \leq k \leq n} C_k\)
, costruisci il grafo
\(f(B) = (N, A)\)
così:
- N è l’insieme delle occorrenze dei letterali in B.
- A è l’insieme \(\{(i,j) | i \in C_k \implies (j \in C_k \text{ e }
i \neq \not j)\}\)
Essendo B in forma normale congiuntiva, è soddisfacibile se e solo se c’è almeno un letterale vero in ogni suo congiunto. Quindi, B è soddisfacibile se e solo se f(B) ha una cricca di ordine pari al numero di congiunti. Una volta trovata la cricca, basta assegnare vero ai letterali corrispondenti ai nodi della cricca. La costruzione garantisce che un nodo, cioè un letterale, non può essere connesso da un arco al nodo originato dallo stesso letterale negato, né può esserlo a un nodo corrispondente a un letterale che compare nello stesso congiunto. La riduzione è logaritmica in spazio perchè basta mantenere sui nastri di lavoro due indici, rappresentati in binario, che scorrono i letterali. □
Problema CIRCUIT SAT
Definizione: un circuito booleano è un grafo diretto aciclico (N, A), i cui nodi 1,…,n sono detti porte e i cui archi sono rappresentati come coppie ordinate: un arco orientato da i a j è rappresentato da (i, j). Le porte hanno 0, 1 o 2 ingressi e sono di sorta \(s(i) \in \{tt,ff,\neg,\wedge,\vee\} \cup X\)
, dove X è l’insieme delle variabili.
Gli ingressi i del circuito sono le porte di sorta \(s(i) \in \{tt,ff\} \cup X\)e non hanno ingresi.
L’uscita del circuito è, per convenzione, la porta n, senza uscite. Tutte le altre porte hanno una uscita e quando \(s(i) = \neg\), la porta i ha un solo ingresso e quando \(s(i) \in \{\wedge, \vee\}\)
allora la porta i ha due ingressi.
Chi ha studiato elettronica digitale si illumini d’immenso:
Il problema della soddisfacibilità dei citcuiti consiste nel decidere se un assegnamento \(\mathcal{V . V}(C) = tt\)
.
In tempo polinomiale non deterministico è possibile trovare l’assegnamento
“giusto” tra i \(2^n\)
possibili, se n sono le variabili e in tempo
polinomiale nel numero di porte del circuito si certifica il risultato.
Problema CIRCUIT VALUE
Definizione: il problema CIRCUIT VALUE consiste nel calcolare il valore di un circuito booleano senza variabili, ovvero gli ingressi del circuito sono porte di sorta \(s(i) \in \{tt,ff\}\)
.
Questo problema appartiene a \(\mathcal{P}\)
: in un circuito di n porte,
basta calcolare livello per livello i valori di uscita. Nonostante le porte siano
disposte ad albero, l’algoritmo lavora su un circuito di n porte, quindi non ci
interessa il fatto che il numero di porte cresca esponenzialmente con il numero
di livelli.
Sul nastro della macchina teniamo i valori calcolati del livello corrente e li
usiamo per calcolare il livello successivo.
Proprietà:
$$\mathrm{CIRCUIT\ VALUE \leq_{LOGSPACE} CIRCUIT\ SAT}$$
Questi due problemi sono strutturalmente simili tra loro, quindi è facilitato il lavoro di trovare una riduzione. In questo caso parliamo di generalizzazione, infatti ogni caso particolare di un problema (di CIRCUIT VALUE) si riduce al problema stesso al caso generale (CIRCUIT SAT) attraverso la funzione identità.
Proprietà:
$$\mathrm{CIRCUIT\ SAT \leq_{LOGSPACE} SAT}$$
Dimostrazione: notiamo che anche CIRCUIT SAT e SAT sono simili tra loro:
entrambi rappresentano funzioni booleane.
Dato il circuito \(C = (N, A)\)
con variabili in X, dobbiamo trovare una
riduzione \(f \in \mathrm{LOGSPACE}\)
tale che l’espressione booleana
\(f(C)\)
sia soddisfacibile se e solo se C lo è. In simboli:
\(\exists \mathcal{V} . [C]_{\mathcal{V}} = tt \iff \exists
\mathcal{V'} . \forall x \in X. \mathcal{V'}(x) = \mathcal{V}(x) \wedge
\mathcal{V'} \models f(C)\)
.
Con l’algoritmo seguente possiamo costruire la funzione \(f(C)\)
:
- le variabili x di \(f(C)\)
sono quelle di C unite a un nuovo insieme che contiene una nuova variabile per ogni porta di C a cui diamo lo stesso nome
- per ogni porta g di C costruiamo i congiunti di \(f(C)\)
- se g è la porta di uscita allora genera il congiunto g
- se \(s(g) = tt\)
allora genera g
- se \(s(g) = ff\)
allora genera \(\neg g\)
- se \(s(g) = x \in X\)
allora genera \((\neg g \vee x) \wedge (g \vee \neg x)\)
, cioè \(g \iff x\)
.
- se \(s(g) = \neg\)
e \((h, g) \in A\)
allora genera \((\neg g \vee \neg h) \wedge (g \vee h)\)
, ovvero \(g \iff \neg h\)
- se \(s(g) = \vee\)
e \((h, g), (k, g) \in A\)
allora genera \((\neg h \vee g) \wedge (\neg k \vee g) \wedge (h \vee k \vee \neg g)\)
, ovvero \(g \iff (h \vee k)\)
.
- se \(s(g) = \wedge\)
e \((h,g),(k,g) \in A\)
allora genera \((\neg g \vee h) \wedge (\neg g \vee k) \wedge (\neg h \vee \neg k \vee g)\)
ovvero \(g \iff (h \wedge k)\)
La dimostrazione che trasformazione richiede spazio logaritmico si basa sulle stesse osservazioni fatte per mostrare che HAM si riduce a SAT (dimostrazione che ho omesso… da migliorare questa parte). □
Corollario:
$$\mathrm{CIRCUIT\ VALUE \leq_{LOGSPACE} SAT}$$
$$\mathrm{CIRCUIT\ VALUE \leq_{LOGSPACE} CRICCA}$$
Dimostrazione: ricordiamo i seguenti fatti:
- \(\mathrm{CIRCUIT\ VALUE \leq_{LOGSPACE} CIRCUIT\ SAT}\)
- \(\mathrm{CIRCUIT\ SAT \leq_{LOGSPACE} SAT}\)
- \(\mathrm{SAT \leq_{LOGSPACE} CRICCA}\)
Quindi:
Per transitività di \(\leq_{\mathrm{LOGSPACE}}\)
ho la tesi.
□
Tabella di computazione di una MdT
Questa definizione ci servirà domani per dimostrare la P-completezza di un problema.
Definizione: la tabella di computazione \(T_M\)
di una macchina di Turing M a 1 nastro deterministica, o semplicemente T quando non vi sia ambiguità, è una matrice quadrata il cui indice di riga i rappresenta l’i-esimo passo di computazione e il cui indice di colonna j rappresenta la j-esima posizione sul nastro. Di conseguenza, la riga i-esima rappresenta la configurazione di M dopo il passo i − 1 e l’elemento T(i, j) contiene il simbolo contenuto nella cella j-esima del nastro dopo i − 1 passi di computazione.
Se M decide il problema I in tempo polinomiale deterministico \(|x|^k\)
,
la sua tabella di computazione (o semplicemente la sua computazione) su x ha
al massimo \(|x|^k\)
righe e altrettante colonne.
Imponiamo anche le seguenti convenzioni:
- il valore di k è tale per cui la macchina M si arresta prima di
\(|x|^k - 2\)
passi. Se \(|x| \leq 1\)
si fa finta che non esista questo caso.
- il nastro è riempito con tanti # quanti ne servono per arrivare alla casella
in colonna \(|x|^k\)
- arricchiamo l’alfabeto di M in modo che la casella \(T(i, j)\)
contenga il nuovo simbolo \(\sigma_q\)
per registrare che nella configurazione i-esima la testina viene a trovarsi sulla j-esima casella, il simbolo letto è \(\sigma\)
e lo stato corrente è q
- la configurazione iniziale parte da \(\triangleright\underline{\sigma}_{q_0}w\)
e non da \(\underline{\triangleright}_{q_0} \sigma w\)
e si saltano i passi di computazione che portano la testina sul respingente per poi riportarla sul primo carattere, eccezion fatta nel caso in cui la macchina termini.
- se \(T(i, j) \in \{\sigma_{SI}, \sigma_{NO}\}\)
allora sposta il cursore fino alla seconda colonna in al massimo \(\mathcal{O}(|x|^k)\)
passi introducendo un nuovo stato di finto arresto.
- se \(\sigma_{SI}\)
oppure \(\sigma_{NO}\)
appaiono nella riga \(p < |x|^k\)
e nella seconda colonna, allora tutte le righe di indice \(q, p \leq q \leq |x|^k\)
sono uguali alla p-esima.
La condizione di terminazione con successo è \(\exists i. T(i, 2) =
\sigma_{SI} = T(|x|^k, 2)\)
.
Osservazione: sia M una macchina di Turing che decide I in \(|x|^k\)
, e T la sua tabella di computazione su x. Abbiamo che
- la cella T(1, 2) contiene lo stato iniziale e il primo carattere di x
- \(\forall j. 2 \leq j \leq |x| + 1\)
, la casella T(1, j) contiene il (j − 1)-esimo simbolo di x (il nastro è inizializzato con l’input)
- \(\forall j. |x| + 2 \leq j \leq |x|^k\)
, la cella T(1, j) contiene # (il nstro di input è vuoto a destra dell’input)
- \(\forall i. T(i, 1) = \triangleright\)
(inizio nastro)
- \(\forall i. T(i, |x|^k) = \#\)
(fine nastro; notare che si impiega meno spazio che tempo!)
Osservazione: il valore di tutti gli altri \(T(i, j)\)
