11. Complessità di spazio

Nel precedente articolo abbiamo valutato la complessità dei problemi computazionali in termini temporali, in questo articolo ne valutiamo la complessità in termini di spazio e di memoria. Tempo e spazio sono due fattori importanti quando bisogna cercare la soluzione ai problemi computazionali. La complessità di spazio condivide molti aspetti della complessità temporale. Per discutere della complessità spaziale utilizzeremo una macchina di Turing. Iniziamo quindi con una prima definizione.

Definizione di complessità di spazio

Denotiamo con M una macchina di Turing deterministica che si arresta su tutti gli input. La complessità di spazio di M è la funzione $f: N \longrightarrow N$, dove f(n) è il numero massimo di celle del nastro che M scandisce su ogni input di lunghezza n. Se la complessità di spazio di M è f(n), allora possiamo dire che M computa in uno spazio f(n).
Se M è una macchina di Turing non deterministica dove tutte le diramazioni si arrestano su tutti gli input, definiamo la sua complessità di spazio f(n) come il massimo numero di celle del nastro che M scandisce su qualsiasi diramazione della sua computazione per ogni input di lunghezza n.

Come per la complessità temporale, anche la complessità di spazio viene stimata attraverso la notazione asintotica. Diamone una definizione:

Definizione di classi di complessità di spazio

Sia $f: N \longrightarrow R^+$ una funzione, le classi di complessità di spazio, SPACE ( f ( n ) ) e NSPACE ( f ( n ) ), sono definite come:

SPACE ( f ( n ) ) = { L | L è un linguaggio deciso da una macchina di Turing deterministica con spazio O( f ( n ) )}.

NSPACE( f ( n ) ) = { L | L è un linguaggio deciso da una macchina di Turing non deterministaca con spazio O ( f ( n ) ) }.

Il teorema di Savitch è uno dei teoremi più importanti nell'ambito della complessità di spazio, in quanto dimostra come le macchine deterministiche possono simulare le macchine non deterministiche attraverso l'uso di una quantità di spazio ridotta. Questo caso viene visto dalla complessità di tempo e dalla complessità di spazio in maniera differente. La prima afferma che tale simulazione richiede un incremento esponenziale in tempo, mentre la seconda mostra come ogni TM non deterministica che usa uno spazio f ( n ) può essere convertita in una TM deterministica che usa soltanto spazio $f^2(n)$. Eunciamo a questo punto il teorema di Savitch.

Teorema di Savitch

Per ogni funzione $f: N \longrightarrow R^+$, dove $f ( n ) \geq n$, $NSPACE ( f ( n ) ) \subseteq SPACE f^2 ( n ) )$.

L'idea alla base della dimostrazione è quella di considerare due configurazioni della NTM $c_1$ e $c_2$ e un numero t. Bisogna verificare se la NTM può transitare da $c_1$ a $c_2$ in al più t passi, usando soltanto lo spazio f(n). Questo problema prende il nome di problema della resa. Risolvere questo problema significa poter stabilire se la macchina accetta il proprio input.

In analogia con la classe P, definiamo la classe PSPACE per la complessità di spazio.

Definizione della classe PSPACE

PSPACE è la classe di linguaggi che sono decidibili in spazio polinomiale con una macchina di Turing deterministica: PSPACE = $\cup_k SPACE ( n^k )$

Definiamo NSPACE come la controparte non deterministica di PSPACE. Inoltre per la classe PSPACE, definiamo la nozione di PSPACE-completezza.

Definizione del concetto di PSPACE-completezza

Un linguaggio B è PSPACE-completo se soddisfa due condizioni:

• B appartiene a PSPACE
• Qualsiasi A appartenente a PSPACE è riducibile in tempo polinomiale a B

Se B soddisfa solo la condizione numero 2, diciamo che è PSPACE-hard.

Nel definire la PSPACE-completezza, usiamo la riducibilità polinomiale. Se riuscissimo a trovare un modo facile per risolvere un problema completo, possiamo risolvere facilmente tutti gli altri problemi nella classe. In questo caso la riduzione deve essere facile, altrimenti se fosse difficile da calcolare, una soluzione facile al problema completo non darebbe necessariamente una soluzione facile ai problemi che ad esso si riducono. Quindi se il modello di riduzione deve essere più limitato del modello usato per definire la classe stessa.