Teorema di Savitch

Nella teoria della complessità computazionale, il teorema di Savitch, dimostrato da Walter Savitch nel 1970, afferma che per ogni funzione $f\left(n\right)\geq n$:

$NSPACE\left(f\left(n\right)\right)\subseteq DSPACE\left(f^{2}\left(n\right)\right)$.

In altre parole, se una macchina di Turing non deterministica è in grado di risolvere un problema in spazio f(n), una macchina di Turing deterministica può risolvere lo stesso problema nel quadrato dello spazio.

Un importante corollario del teorema è che PSPACE = NPSPACE. Ciò deriva dal fatto che il quadrato di una funzione polinomiale è a sua volta una funzione polinomiale.

Grafo orientato delle configurazioni della macchina di Turing

Il teorema di Savitch codifica attraverso un grafo orientato le configurazioni di una macchina di Turing. Ogni nodo del grafo rappresenta una configurazione. Tra due nodi u e v esiste un arco orientato se dalla configurazione u è possibile raggiungere la configurazione v.

Il problema di decidere un linguaggio si trasforma in un problema di raggiungibilità su grafi orientati. Nello specifico si tratta di capire se dalla configurazione iniziale è possibile raggiungere una qualunque configurazione di accettazione.

Algoritmo usato per la dimostrazione

Viene presentato un algoritmo che in base ad una stringa w data come ingresso ad una macchina di Turing N, due configurazioni c₁, c₂ ed un ingresso t, restituisce true se dalla configurazione c₁ è possibile raggiungere la configurazione c₂ in almeno t passi.

PuoRaggiungere(c₁, c₂,t)

1. Se t = 1, verifica se c₁ = c₂ o se c₁ restituisce c2 in base alle regole di N. Restituisci true se almeno una delle condizioni si verifica, false altrimenti
2. Se t > 1, allora per ogni configurazione c_m di N su w usando spazio f(n):
   1. Esegui PuoRaggiungere(c₁, c_m, ParteInteraSuperiore(t/2)).
   2. Esegui PuoRaggiungere(c_m, c₂, ParteInteraSuperiore(t/2)).
   3. Se entrambi i due passi precedenti hanno restituito true, restituisci true.
3. Se non hai ancora restituito true, restituisci false.

In questo algoritmo, la funzione ParteInteraSuperiore restituisce la parte intera superiore del valore che viene passato come argomento.

La prima chiamata a questa funzione ricorsiva viene fatta con la tripletta di parametri (c_iniziale, c_finale,2^df(n)), dove d è una costante scelta appositamente in modo che la macchina di Turing N non abbia più di 2^df(n) configurazioni usando un nastro di f(n) celle.

Bibliografia

• (EN) Sanjeev Arora, Bazra Barak, Computational complexity: a modern approach, 2009, Cambridge University Press, ISBN 978-0-521-42426-4.
• Michael Sipser, Introduction to the Theory Of Computation, Terza Edizione, Cengage Learning, 2013, ISBN 978-1-133-18779-0.