Teorema lui Savitch

În teoria complexității de calcul , teorema lui Savitch , demonstrată de Walter Savitch în 1970 ^[1] , afirmă că pentru fiecare funcție $f\left(n\right)\geq n$ ${\ displaystyle f \ left (n \ right) \ geq n}$ ${\ displaystyle f \ left (n \ right) \ geq n}$ :

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

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

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

.

Cu alte cuvinte, dacă o mașină de Turing nedeterministă poate rezolva o problemă în spațiul f ( n ), o mașină de Turing deterministă poate rezolva aceeași problemă în pătratul spațiului.

Un corolar important al teoremei este că PSPACE = NPSPACE . Acest lucru rezultă din faptul că pătratul unei funcții polinomiale este în sine o funcție polinomială.

Grafic direcționat al configurațiilor mașinii Turing

Teorema lui Savitch codifică configurațiile unei mașini Turing printr-un grafic orientat. Fiecare nod al graficului reprezintă o configurație. Între două noduri u și v există un arc orientat dacă din configurația u este posibil să se ajungă la configurația v .

Problema de a decide un limbaj se transformă într-o problemă de accesibilitate pe grafice orientate. Mai exact, este vorba de a înțelege dacă se poate ajunge la orice configurație de acceptare din configurația inițială.

Algoritm folosit pentru demonstrație

Este prezentat un algoritm care pe baza unui șir w dat ca intrare la o mașină Turing N , două configurații c ₁ , c ₂ și o intrare t , returnează adevărat dacă din configurația c ₁ este posibil să se ajungă la configurația c ₂ în la cel puțin t pași.

Poate ajunge ( c ₁ , c ₂ , t )

Dacă t = 1, verificați dacă c ₁ = c ₂ sau dacă c ₁ returnează c2 conform regulilor din N. Returnează adevărat dacă cel puțin una dintre condiții este adevărată , în caz contrar este falsă
Dacă t > 1, atunci pentru orice configurație c _m de N pe w folosind spațiul f (n) :
1. Executați CanReach ( c ₁ , c _m , partea totală superioară ( t / 2));
2. Run Can Reach ( c _m , c ₂ , partea totală superioară ( t / 2));
3. Dacă ambii pași anteriori au revenit adevărat , reveniți la adevărat .
Dacă nu v-ați întors încă adevărat , reveniți la fals .

În acest algoritm, funcția UpperIntegerPart returnează partea întreagă superioară a valorii care este transmisă ca argument.

Primul apel la această funcție recursivă se face cu tripletul de parametri ( c _inițial , c _final , 2 ^{df (n)} ), unde d este o constantă aleasă în mod specific, astfel încât mașina Turing N să nu aibă mai mult de 2 ^{df (n)} configurații folosind o panglică de celule f (n) .

Notă

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

Bibliografie

( EN ) Sanjeev Arora, Bazra Barak, Complexitatea calculațională : o abordare modernă , 2009, Cambridge University Press, ISBN 978-0-521-42426-4 .
Michael Sipser, Introducere în teoria calculelor , ediția a treia, Cengage Learning, 2013, ISBN 978-1-133-18779-0 .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

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

[1]