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

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

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

Доказ

Доказ теореме демонстрира алгоритам STCON – утврђивање да ли постоји путања између два чвора усмереног графа, који се извршава у простору ${\displaystyle O\left((\log n)^{2}\right)}$ са 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) битова меморије за складиштење аргумената и локалних променљивих, тако да је укупан, потребан меморијски простор за извршење алгоритма ${\displaystyle O\left((\log n)^{2}\right)}$. Иако је приказани алгоритам овде описан вишим програмским језиком, он може да се имплементира и на Тјуринговој машини и захтеви за меморијским простором потребним за извршење алгоритма ће остати исти.

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

Последице

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

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