Il tempo non è l'unica risorsa che conta. Un algoritmo può essere veloce ma richiedere troppa memoria, oppure lento ma frugale. La complessità spaziale studia quanta memoria serve per risolvere un problema. I risultati sono diversi, e per certi versi più netti, di quelli sul tempo: lo spazio si può riutilizzare, mentre il tempo, una volta speso, è perso. Questa semplice osservazione cambia molte cose.
Le definizioni
Per una macchina di Turing che si ferma su ogni input, lo spazio usato è il numero massimo di celle del nastro visitate su un input di lunghezza n.
- SPACE(f(n)): linguaggi decisi da una macchina deterministica in spazio O(f(n)).
- NSPACE(f(n)): lo stesso per macchine non deterministiche, in cui ogni ramo usa al più quello spazio.
- PSPACE: unione di SPACE(nᵏ) per ogni k, cioè i problemi risolvibili con memoria polinomiale.
Per lo spazio sublineare, come log n, si usa un modello a due nastri: un nastro di input a sola lettura, che non viene contato, e un nastro di lavoro, che è l'unico misurato. Altrimenti già leggere l'input occuperebbe n celle.
Relazioni con il tempo
Due osservazioni collegano tempo e spazio:
- Lo spazio non supera il tempo. In t passi una macchina visita al più t celle. Quindi P ⊆ PSPACE e NP ⊆ PSPACE.
- Il tempo è al più esponenziale nello spazio. Una macchina che usa s celle ha un numero di configurazioni distinte limitato da 2^O(s). Se si ferma, non può ripetere una configurazione, altrimenti andrebbe in ciclo. Quindi PSPACE ⊆ EXPTIME.
Mettendo tutto insieme:
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
Sappiamo che P ≠ EXPTIME, ma non quale delle inclusioni intermedie sia stretta.
Perché NP sta in PSPACE
Il primo punto si vede anche direttamente per SAT. Si provano tutti i 2ⁿ assegnamenti uno dopo l'altro, riusando sempre lo stesso spazio: si scrive un assegnamento, si valuta la formula, si cancella e si passa al successivo. Il tempo è esponenziale, ma la memoria resta lineare.
Il teorema di Savitch
Per il tempo non sappiamo se il non determinismo si possa eliminare a costo polinomiale. Per lo spazio sì:
per ogni f(n) ≥ log n, NSPACE(f(n)) ⊆ SPACE(f(n)²).
Il non determinismo costa al più un quadrato in spazio. Di conseguenza PSPACE = NPSPACE.
L'idea della dimostrazione
Si vuole sapere se una macchina non deterministica può passare dalla configurazione iniziale a quella accettante in al più t passi. Si definisce una procedura RAGGIUNGI(c₁, c₂, t):
- se t = 1, controlla direttamente se c₂ segue da c₁ in un passo;
- altrimenti, per ogni possibile configurazione intermedia m: - se RAGGIUNGI(c₁, m, t/2) e RAGGIUNGI(m, c₂, t/2) sono entrambe vere, rispondi sì;
- se nessuna m funziona, rispondi no.
Il tempo è enorme, perché si provano tutte le configurazioni intermedie. Ma lo spazio è contenuto: la profondità della ricorsione è log t, e ogni livello memorizza solo poche configurazioni di dimensione O(f(n)). Poiché t è al più 2^O(f(n)), la profondità è O(f(n)) e lo spazio totale O(f(n)²).
Il punto chiave è che le due chiamate ricorsive riusano lo stesso spazio: prima si esegue la prima, si cancella il lavoro, poi si esegue la seconda.
Un problema PSPACE-completo: TQBF
Una formula booleana quantificata pienamente ha tutte le variabili legate da quantificatori:
∀x ∃y [(x ∨ y) ∧ (¬x ∨ ¬y)]
Questa formula è vera: per ogni valore di x esiste un y, il suo opposto, che soddisfa la parte fra parentesi.
TQBF = {⟨φ⟩ : φ è una formula booleana pienamente quantificata vera}
TQBF è PSPACE-completo: sta in PSPACE e ogni problema in PSPACE vi si riduce in tempo polinomiale.
- TQBF ∈ PSPACE: si valuta ricorsivamente. Per ∃x si provano x = 0 e x = 1 e basta che uno funzioni; per ∀x devono funzionare entrambi. La profondità della ricorsione è il numero di variabili, e ogni livello usa spazio costante.
- Completezza: la riduzione riprende l'idea del teorema di Savitch, codificando la procedura RAGGIUNGI con quantificatori che evitano di duplicare la formula a ogni livello.
Il legame con i giochi
L'alternanza ∃∀∃∀ ricorda una partita a due: «esiste una mia mossa tale che per ogni tua risposta esiste una mia mossa…». Per questo molti giochi generalizzati a scacchiera n × n sono PSPACE-completi o ancora più difficili. Un esempio classico è la geografia generalizzata: su un grafo orientato i due giocatori muovono a turno una pedina lungo gli archi senza ripassare per un nodo già visitato, e perde chi non può muovere. Decidere se il primo giocatore ha una strategia vincente è PSPACE-completo.
Spazio logaritmico: L e NL
All'estremo opposto ci sono le classi con memoria minuscola:
- L = SPACE(log n): bastano pochi contatori e puntatori nell'input;
- NL = NSPACE(log n): la versione non deterministica.
Il problema della raggiungibilità in un grafo orientato è NL-completo. Per Savitch sta in SPACE(log² n). Un altro risultato notevole, il teorema di Immerman-Szelepcsényi, mostra che NL = coNL: a differenza di quanto si congettura per NP, la classe è chiusa per complemento. Valgono L ⊆ NL ⊆ P, e anche qui le inclusioni strette restano aperte.
In sintesi
- Lo spazio si riutilizza, e per questo le classi spaziali si comportano diversamente da quelle temporali.
- P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, con P ≠ EXPTIME.
- Il teorema di Savitch mostra che il non determinismo costa al più un quadrato in spazio: PSPACE = NPSPACE.
- TQBF è PSPACE-completo, e molti giochi generalizzati lo sono per la stessa struttura alternata.
- Nello spazio logaritmico, la raggiungibilità è NL-completa e vale NL = coNL.
