Севичева теорема

У рачунарској теорији сложености, Севичева теорема коју је 1970. године доказао Валтер Севич, даје релацију између детерминистичког и недетерминистичког простора сложености. Она утврђује да за било коју функцију $f\in \mathrm{\Omega }(\log (n))$, важи :$\text{NSPACE}\left(f\left(n\right)\right)\subseteq \text{DSPACE}\left({\left(f\left(n\right)\right)}^2\right).$

Другим речима, ако недетерминистичка Тјурингова машина може да реши проблем у меморијском простору f (n), обична, детерминистичка Тјурингова машина може да реши исти проблем у меморијском простору који је на квадрат већи. Иако се чини да недетерминизам, временом, може да обезбеди експоненцијалне добитке, ова теорема показује да је његов утицај на потребе за меморијским простором у значајној мери ограничен.

Доказ

Доказ теореме демонстрира алгоритам STCON – утврђивање да ли постоји путања између два чвора усмереног графа, који се извршава у простору $O((\log n{)}^2)$ са n чворова. Основна идеја алгоритма је да рекурзивно реши нешто општији проблем, проверавајући да ли постоји путања од чвора s до чвора t која користи највише k грана, где је k улазни параметар рекурзивног алгоритма. STCON може да се користи за решење овог проблема постављањем k на вредност n. Да би се проверило да ли постоји путања од k грана између чворова s и t, приступ може да буде да се за сваки чвор u графа провери да ли се налази на траженој путањи рекурзивном претрагом путања између чворова s до u и u до t. Користећи псеудокод (синтакса слична језику Пајтон) алгоритам може да се прикаже на следећи начин.

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

Функција претраге путања позива саму себе до рекурзивне дубине O(log n) и за сваки позив користи O(log n) битова меморије за складиштење аргумената и локалних променљивих, тако да је укупан, потребан меморијски простор за извршење алгоритма $O((\log n{)}^2)$. Иако је приказани алгоритам овде описан вишим програмским језиком, он може да се имплементира и на Тјуринговој машини и захтеви за меморијским простором потребним за извршење алгоритма ће остати исти.

Разлог, зашто приказани алгоритам имплицира теорему је тај, што било који језик $L\in \text{NSPACE}\left(f\left(n\right)\right)$ одговара усмереном графу чији чворови представљају $O\left(2^{f(n)}\right)$ конфигурација Тјурингове машине који припадају $L$. За свако $x\in \{0,1{\}}^n$, овај граф има путању од почетне конфигурације за улаз $x$ до прихватне конфигурације, ако и само ако важи да $x\in L$. Тако је одговарајућа повезаност довољна да се одлучи о припадности $L$ и приказани алгоритам може да се изврши у меморијском простору $\text{DSPACE}\left({\left(f\left(n\right)\right)}^2\right)$.

Последице

Неке од важних последица теореме су следеће:

• PSPACE = NPSPACE – ово директно следи из чињенице да је квадрат полинома и даље полином,
• NL ⊆ L² - STCON је NL комплетан тако да сви језици који припадају NL, такође припадају класи сложености L² = $\text{DSPACE}\left({(\log n)}^2\right)$.

Литература

• Шаблон:Cite book
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation

Спољашње везе

• 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.