Sevičeva teorema

U računarskoj teoriji složenosti, Sevičeva teorema koju je 1970. godine dokazao Valter Sevič, daje relaciju između determinističkog i nedeterminističkog prostora složenosti. Ona utvrđuje da za bilo koju funkciju $f\in \Omega (\log(n))$, važi :${\text{NSPACE}}\left(f\left(n\right)\right)\subseteq {\text{DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).$

Drugim rečima, ako nedeterministička Tjuringova mašina može da reši problem u memorijskom prostoru f (n), obična, deterministička Tjuringova mašina može da reši isti problem u memorijskom prostoru koji je na kvadrat veći. Iako se čini da nedeterminizam, vremenom, može da obezbedi eksponencijalne dobitke, ova teorema pokazuje da je njegov uticaj na potrebe za memorijskim prostorom u značajnoj meri ograničen.

Dokaz

Dokaz teoreme demonstrira algoritam STCON – utvrđivanje da li postoji putanja između dva čvora usmerenog grafa, koji se izvršava u prostoru $O\left((\log n)^{2}\right)$ sa n čvorova. Osnovna ideja algoritma je da rekurzivno reši nešto opštiji problem, proveravajući da li postoji putanja od čvora s do čvora t koja koristi najviše k grana, gde je k ulazni parametar rekurzivnog algoritma. STCON može da se koristi za rešenje ovog problema postavljanjem k na vrednost n. Da bi se proverilo da li postoji putanja od k grana između čvorova s i t, pristup može da bude da se za svaki čvor u grafa proveri da li se nalazi na traženoj putanji rekurzivnom pretragom putanja između čvorova s do u i u do t. Koristeći pseudokod (sintaksa slična jeziku Pajton) algoritam može da se prikaže na sledeći način.

def k_edge_path(s, t, k):
    if k == 0:
        return s == t
    if k == 1:
        return s == t or (s, t) in edges
    for u in vertices:
        if k_edge_path(s, u, floor(k / 2)) and k_edge_path(u, t, ceil(k / 2)):
            return true
    return false

Funkcija pretrage putanja poziva samu sebe do rekurzivne dubine O(log n) i za svaki poziv koristi O(log n) bitova memorije za skladištenje argumenata i lokalnih promenljivih, tako da je ukupan, potreban memorijski prostor za izvršenje algoritma $O\left((\log n)^{2}\right)$. Iako je prikazani algoritam ovde opisan višim programskim jezikom, on može da se implementira i na Tjuringovoj mašini i zahtevi za memorijskim prostorom potrebnim za izvršenje algoritma će ostati isti.

Razlog, zašto prikazani algoritam implicira teoremu je taj, što bilo koji jezik $L\in {\text{NSPACE}}\left(f\left(n\right)\right)$ odgovara usmerenom grafu čiji čvorovi predstavljaju $O\left(2^{f(n)}\right)$ konfiguracija Tjuringove mašine koji pripadaju $L$. Za svako $x\in \{0,1\}^{n}$, ovaj graf ima putanju od početne konfiguracije za ulaz $x$ do prihvatne konfiguracije, ako i samo ako važi da $x\in L$. Tako je odgovarajuća povezanost dovoljna da se odluči o pripadnosti $L$ i prikazani algoritam može da se izvrši u memorijskom prostoru ${\text{DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right)$.

Posledice

Neke od važnih posledica teoreme su sledeće:

• PSPACE = NPSPACE – ovo direktno sledi iz činjenice da je kvadrat polinoma i dalje polinom,
• NL ⊆ L² - STCON je NL kompletan tako da svi jezici koji pripadaju NL, takođe pripadaju klasi složenosti L² = ${\text{DSPACE}}\left(\left(\log n\right)^{2}\right)$.

Literatura

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112. 
• Papadimitriou, Christos (1993), „Section 7.3: The Reachability Method”, Computational Complexity (1st izd.), Addison Wesley, str. 149—150, ISBN 978-0-201-53082-7 
• Savitch, Walter J. (1970), „Relationships between nondeterministic and deterministic tape complexities”, Journal of Computer and System Sciences, 4 (2): 177—192, doi:10.1016/S0022-0000(70)80006-X 
• Sipser, Michael (1997), „Section 8.1: Savitch's Theorem”, Introduction to the Theory of Computation, PWS Publishing, str. 279—281, ISBN 978-0-534-94728-6 

Spoljašnje veze

• Lance Fortnow, Foundations of Complexity, Lesson 18: Savitch's Theorem. Accessed 09/09/09.
• Richard J. Lipton, Savitch’s Theorem. Gives a historical account on how the proof was discovered.