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.
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 c1 a quella finale c2 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
Si Consideri una MdT non deterministica arbitraria N.
Preso un intero t positivo, e due configurazioni c1 e c2 di N. Diremo che c1 produce c2 in un numero minore di passi t se N può andare da c1 a c2 in t o meno passi.
Il seguente algoritmo ricorsivo deterministico decide il problema della “produzione” quando t è una potenza del 2 (t=2p per qualche p maggiore o uguale a 0).
CANYIELD(c1, c2, 2p) = “Con input c1,c2 e p, dove p≥0 e c1,c2 sono configurazioni che usano al più spazio f(n) (se lo spazio occupato è minore possiamo raggiungere spazio f(n) aggiungendo caratteri blank):
Passiamo adesso a definire la MdT deterministica che simula N. Prima abbiamo bisogno di fare alcune assunzioni semplificative (senza perdita di generalità):
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(cstart, caccept, 2d*f(n)) .”
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 c1,c2 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(f2(n)), come voluto.
Ritorniamo per un momento sull’affermazione
M = “Su input w: L’output è il risultato di CANYIELD(cstart, caccept, 2d*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:
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(f2(n)).
Definizione: PSPACE è la classe dei linguaggi che sono decisi in spazio polinomiale da macchine di Turing deterministiche. In altre parole,
PSPACE = SPACE(n) ∪ SPACE(n2) ∪ SPACE(n3) ∪ …
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).
4. Macchine di Turing multinastro
5. Macchine di Turing non-deterministiche
6. Macchina di Turing universale e problema della fermata
7. Problemi decidibili e non decidibili
8. Problemi non decidibili e riducibilità - prima parte
9. Problemi non decidibili e riducibilità - seconda parte
11. Decidibilità delle teorie logiche
12. Misurazione della Complessità e introduzione alla classe P
14. NP-Completezza - prima parte
15. NP-Completezza - seconda parte
16. Altri problemi NP-Completi
17. Esercitazione su problemi NP-Completi
18. Space Complexity
19. Savitch Theorem