Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 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 del teorema di Savitch

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):

  1. Se p=0, allora “test se c1=c2” oppure “c1 produce c2 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(c1, cm, 2p-1).
  4. Run CANYIELD(cm, c2, 2p-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(cstart, caccept, 2d*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 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.

Dimostrazione del teorema di Savitch

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:

  • Utilizzando CANYIELD, controlla che qualche configurazione che utilizzano più di i celle del nastro sia raggiungibile da cstart.
  • 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(f2(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(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).

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion