Teorema di Savitch

Da Wikipedia, l'enciclopedia libera.

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

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

PuoRaggiungere(c1, c2,t)

  1. Se t = 1, verifica se c1 = c2 o se c1 restituisce c1 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 cm di N su w usando spazio f(n):
    1. Esegui PuoRaggiungere(c1, cm, ParteInteraSuperiore(t/2));
    2. Esegui PuoRaggiungere(cm, c2, 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 (ciniziale, cfinale,2df(n)), dove d è una costante scelta appositamente in modo che la macchina di Turing N non abbia più di 2df(n) configurazioni usando un nastro di f(n) celle.

Note[modifica | modifica sorgente]

  1. ^ Walter J. Savitch, Relationships between nondeterministic and deterministic tape complexities in Journal of Computer and System Sciences, vol. 4, nº 2, 1970, pp. 177–192, DOI:10.1016/S0022-0000(70)80006-X.

Bibliografia[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica