Aniello Murano » 19.Savitch Theorem

Teorema di Savitch

Si ricordi che una macchina di Turing deterministica M può sempre simulare una corrispondente macchina di Turing M’ non deterministica con una complessità di tempo esponenziale rispetto alla taglia di M.
Il seguente teorema di Savitch dimostra invece che nello spazio la complessità di questa simulazione aumenta in modo al più quadratico.
Teorema di Savitch: Per ogni funzione f: N→R⁺, dove f(n)≥n, abbiamo

NSPACE(f(n)) ⊆ SPACE(f2(n)).

La dimostrazione di questo teorema rivela che una MdT deterministica può simulare una TM non deterministica usando soltanto una piccola parte di spazio aggiuntivo.
Questo è dovuto al fatto che lo spazio può essere riutilizzato, mentre il tempo no.
Se potessimo utilizzare lo stesso concetto con il tempo avremmo una prova che P=NP.

Preambolo alla dimostrazione del teorema di Savitch

Si consideri una MdT non deterministica N di spazio f(n).
Cerchiamo di simularne il comportamento con una MdT deterministica con spazio polinomiale in f(n).
Un primo tentativo potrebbe essere quello di simulare tutti i possibili rami di computazione di N, ma questo non permette di sovrascrivere l’area di memoria utilizzata, perché occorre tenere traccia delle scelte nondeterministiche fatte su un ramo specifico per scegliere un prossimo ramo. Le scelte fatte su un ramo sono esponenziali in numero (anche se lo spazio è polinomiale). Dunque, questo tentativo richiede spazio esponenziale.
Una soluzione polinomiale è invece offerta dalla soluzione (in spazio polinomiale) di un problema intermedio, che consiste nel verificare se N su un generico input w può passare da una configurazione iniziale c₁ a quella finale c₂ in un numero di passi minore o uguale a un numero dato t (intuitivamente, t è il numero massimo di operazioni che N necessita per accettare w).
Chiamiamo questo problema yieldability problem, e lo risolviamo definendo la MdT deterministica ricorsiva CANYIELD definita nella prossima diapositiva.

Dimostrazione del teorema di Savitch

Dimostrazione
Si Consideri una MdT non deterministica arbitraria N.
Preso un intero t positivo, e due configurazioni c₁ e c₂ di N. Diremo che c1 produce c2 in un numero minore di passi t se N può andare da c₁ a c₂ in t o meno passi.
Il seguente algoritmo ricorsivo deterministico decide il problema della “produzione” quando t è una potenza del 2 (t=2^p per qualche p maggiore o uguale a 0).

CANYIELD(c₁, c₂, 2^p) = “Con input c₁,c₂ e p, dove p≥0 e c₁,c₂ sono configurazioni che usano al più spazio f(n) (se lo spazio occupato è minore possiamo raggiungere spazio f(n) aggiungendo caratteri blank):

1. Se p=0, allora “test se c₁=c₂” oppure “c₁ produce c₂ in un solo step” in base alle derivazioni di N. Accept se il test ha successo, altrimenti rejectl.
2. Se p>0, allora per ciascuna configurazione cm di N che usa spazio ≤f(n):
3. Run CANYIELD(c₁, c_m, 2^p-1).
4. Run CANYIELD(c_m, c₂, 2^p-1).
5. Se lo step 3 e 4 entrambi accept, allora accept.
6. Se non hanno entrambi accettato allora, reject.”

Dimostrazione del teorema di Savitch

Passiamo adesso a definire la MdT deterministica che simula N. Prima abbiamo bisogno di fare alcune assunzioni semplificative (senza perdita di generalità):

• Quando N accetta, prima di fermarsi pulisce il nastro e ritorna all’inizio del nastro, dove entrerà in una (fissata) configurazione chiamata caccept.
• Con w indichiamo l’input generico di N, n è la lunghezza di w e cstart è la configurazione iniziale di N su w.

Denotiamo con d una costante tale che N non usa più di 2d*f(n) configurazioni per computare w. In pratica, 2d*f(n) fornisce un upper bound per il tempo di esecuzione di N su w.
Con queste assunzioni, abbiamo che N accetta w se e solo se può andare da cstart a caccept in 2d*f(n) passi o meno. Di conseguenza, la seguente MdT deterministica M simula N se:

M = “”Su input w:
L’output è il risultato di CANYIELD(c_start, c_accept, 2^d*f(n)) .”

Dimostrazione del teorema di Savitch 3

Visto che CANYIELD risolve l’yieldability problem, M simula correttamente N.
Rimane adesso da analizzare la complessità di spazio di M.
Ogni volta che CANYIELD invoca se stesso ricorsivamente, memorizza lo stato corrente e i valori c₁,c₂ e p così da poter essere richiamati al ritorno dalla ricorsione.
Ciascun livello della ricorsione quindi usa spazio O(f(n)) aggiuntivo.
Il numero delle chiamate ricorsive è invece pari a d*f(n).
Dunque, lo spazio totale usato da N è d*f(n)*O(f(n))=O(f²(n)), come voluto.

Dimostrazione del teorema di Savitch

Ritorniamo per un momento sull’affermazione
M = “Su input w: L’output è il risultato di CANYIELD(c_start, c_accept, 2^d*f(n))”

C’è una cosa che sembra esserci sfuggito: M deve sapere il valore di f(n) quando invoca CANYIELD!
Un modo semplice per risolvere questo problema è quello di modificare M (in M’) in modo che provi per f(n) = 1,2,3, … Per ogni valore f(n) = i, M’ usa CANYIELD per accettare e determinare se la configurazione è raggiungibile (accetta se è questo è il caso).
Per garantire che M’ non continui ad aumentare i (e quindi a consumare spazio) nei casi in cui N non accetta w, M’ effettua il seguente controllo prima di passare da i a i+1:

• Utilizzando CANYIELD, controlla che qualche configurazione che utilizzano più di i celle del nastro sia raggiungibile da c_start.
• Se ciò non avviene, non ha alcun senso cercare per i+1, e quindi M’ va in reject.

Per memorizzare il valore i occorre spazio O(log f(n)). Inoltre, questo spazio può essere riciclato ad ogni iterazione.
Dunque, la complessità dello spazio di M’ rimane O(f²(n)).

Definizione di classe Pspace

Definizione: PSPACE è la classe dei linguaggi che sono decisi in spazio polinomiale da macchine di Turing deterministiche. In altre parole,

PSPACE = SPACE(n) ∪ SPACE(n²) ∪ SPACE(n³) ∪ …

NPSPACE può essere definita in modo simile. Tuttavia, quest’ultima non è una classe molto interessante perché, come sappiamo dalle conseguenze del teorema di Savitch, coincide con PSPACE.

Questo è quello che conosciamo:

P ⊆ NP ⊆ PSPACE=NPSPACE ⊆ EXPTIME.

Tuttavia non conosciamo se qualcuna delle inclusioni possa essere sostituita con un uguaglianza (un altro dei problemi aperti). Tuttavia però possiamo provare che

P≠EXPTIME.

Quindi sappiamo con sicurezza che l’ultima delle tre inclusioni deve essere necessariamente un inclusione (non un uguaglianza).