Per studiare la complessità in spazio andiamo a definire un’altra variante di macchine di Turing composte dai seguenti nastri in ordine:

1. un nastro in sola lettura dedicato a contenere il dato di ingresso
2. altri k - 2 nastri in lettura e scrittura, equivalenti a quelli di una MdT a k - 2 nastri normale
3. un nastro in sola scrittura dedicato a contenere il dato di uscita

Macchina di Turing I/O

Definizione: una MdT con k nastri \(M = (Q, \Sigma, \delta, q_0)\) è di tipo I/O se e solo se la funzione di transizione δ è tale che \(\delta(q,\sigma_1,...,\sigma_k) = (q', (\sigma'_1, D_1), ..., (\sigma'_k, D_k))\) ed è vero che:

• il primo nastro è in sola lettura cioè \(\sigma'_1 = \sigma_1\)
• l’ultimo nastro è in sola scrittura cioè \(D_k = R \lor D_k = - \implies \sigma'_k = \sigma_k\)
• la macchina visita al massimo una cella bianca a destra del dato di ingresso cioè \(\sigma_1 = \# \implies D_1 \in \{ L, - \}\)

Proprietà: per ogni MdT con k nastri M che decide I in tempo deterministico f, esiste una MdT a k + 2 nastri \(M'\) di tipo I/O che decide I in tempo deterministico \(c \times f\) , per qualche costante c.

Dimostrazione: la macchina \(M'\) :

1. copia il primo nastro di M sul proprio ultimo nastro, impiegando \(|x| + 1\) passi
2. opera come M senza più toccare il proprio primo nastro, impiegando \(f(|x|)\) passi
3. copia il risultato del calcolo di M sul proprio ultimo nastro, in al più \(f(|x|)\) passi e termina

In totale la macchina \(M'\) ha richiesto su x un numero di passi inferiore o uguale a \(|x| + 1 + f(|x|) + f(|x|) = 2 \times f(|x|) + |x| + 1\) . Quindi \(cf = 2f + y \implies c = 2 + y\) con \(y = |x| + 1\) e ho dimostrato che \(M'\) a k nastri con I/O esiste. □

Complessità in spazio deterministico

Per misurare lo spazio richiesto da una MdT, ne modifichiamo una in modo che tenga traccia delle caselle visitate. La modifica consiste nell’usare il simbolo \(\triangleleft \notin \Sigma\) per delimitare fin dove è arrivata la testina, cioè la funzione di transiszione sposta implicitamente ◁ a destra ogni volta che la testina si sposterebbe sopra a ◁.

Per esempio la computazione della macchina che calcola se la stringa aba è palindroma sarebbe:

Definizione: sia M una MdT a k nastri di tipo I/O tale che

$$\forall x (q_0,\underline{\triangleright}x, \underline{\triangleright},...,\underline{\triangleright}) \mapsto^\star (H,w_1,w_2,...,w_k) \text{ con } H \in \{SI, NO\}$$

Lo spazio richiesto da M per decidere x è

$$\sum^{k-1}_{i=2}|w_i|$$

Inoltre M decide I in spazio deterministico f(n) se per ogni x lo spazio richiesto da M per decidere x è minore o uguale a f(|x|).
Infine, se M decide I in spazio deterministico f(n), allora

$$I \in \mathrm{SPACE}(f(n))$$

Notiamo che la sommatoria della definizione sopra esclude il primo e l’ultimo nastro (che sono rispettivamente il nastro del dato in ingresso e in uscita). Il motivo è che se considerassimo anche questi nastri non potrebbe esistere una complessità in spazio sub-lineare: dovrei sempre contare l’intera lunghezza del dato di ingresso e di uscita, schiacciando \(\mathrm{LOGSPACE}(n) \text{ su } \mathrm{PSPACE}(n)\) .

Come fatto per la classe dei problemi decidibili in tempo polinomiale deterministico P, introduciamo la classe dei problemi in spazio deterministico polinomiale e, in più, quelli in spazio deterministico logaritmico:

Complessità in spazio deterministico polinomiale e logaritmico

Definizione:

$$\mathrm{PSPACE} = \bigcup_{k \geq 1} \mathrm{SPACE} (n^k)$$

Definizione:

$$\mathrm{LOGSPACE} = \bigcup_{k \geq 1} \mathrm{SPACE} (k \times \log n)$$

Anche queste due classi sono invarianti al cambio di modelli e sono chiuse rispetto alla trasformazione di modelli, il che garantisce la loro robustezza.

Teorema di compressione lineare dello spazio

Questo teorema è l’analogo in spazio del teorema di accelerazione lineare.

Teorema: se \(I \in \mathrm{SPACE}(f(n))\) , allora:

$$\forall \epsilon \in \mathbb{R}^+ . I \in \mathrm{SPACE} (2 + \epsilon \times f(n))$$

Gerarchia

Teorema:

$$\mathrm{LOGSPACE} \subsetneq \mathrm{PSPACE}$$

I problemi che si possono risolvere avendo a disposizione una quantità logaritmica di caselle rispetto alla taglia dell’input, sono un sottoinsieme proprio dell’insieme dei problemi che si possono risolvere avendo “più spazio” a disposizione, cioè spazio polinomiale nella taglia di x.
Non dimostriamo questo teorema.

Teorema:

$$\mathrm{LOGSPACE} \subseteq \mathcal{P}$$

Dimostrazione: poiché \(I \in \mathrm{LOGSPACE} \subseteq \mathcal{P}\) , c’è una MdT che decide ogni sua istanza \(x \in I\) in \(\mathcal{O}(\log |x|)\) spazio deterministico. Tale MdT ha un numero finito di configurazioni non terminali possibili. Contiamole (tralasciando le costanti):

• \(|x|\) lunghezza dell’input
• \(\log |x|\) lunghezza della memoria aggiuntiva
• \(\#Q\) stati possibili
• \(\#\Sigma^{\log |x|}\) possibili stringhe di memoria aggiuntiva

Di conseguenza la MdT può attraversare \(\mathcal{O}(|x| \times \log |x| \times \#Q \times \#\Sigma^{\log |x|})\) configurazioni non terminali diverse. Una computazione non può ripassare su una stessa configurazione, altrimenti va in ciclo, quindi una computazione compie al massimo un numero di passi polinomiale della taglia di x, ovvero \(\mathcal{O}(|x|^k)\) passi per qualche k. □

Osservazione: lo spazio limita il tempo

Da questa dimostrazione possiamo arrivare al duale di quanto affermato ieri, cioè che nel caso di algoritmi per problemi decidibili lo spazio limita il tempo di calcolo.