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

Из Википедије, слободне енциклопедије

У рачунарској теорији сложености, Севичева теорема коју је 1970. године доказао Валтер Севич, даје релацију између детерминистичког и недетерминистичког простора сложености. Она утврђује да за било коју функцију , важи :

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

Доказ[уреди]

Доказ теореме демонстрира алгоритам STCON – утврђивање да ли постоји путања између два чвора усмереног графа, који се извршава у простору са 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) битова меморије за складиштење аргумената и локалних променљивих, тако да је укупан, потребан меморијски простор за извршење алгоритма . Иако је приказани алгоритам овде описан вишим програмским језиком, он може да се имплементира и на Тјуринговој машини и захтеви за меморијским простором потребним за извршење алгоритма ће остати исти.

Разлог, зашто приказани алгоритам имплицира теорему је тај, што било који језик одговара усмереном графу чији чворови представљају конфигурација Тјурингове машине који припадају . За свако , овај граф има путању од почетне конфигурације за улаз до прихватне конфигурације, ако и само ако важи да . Тако је одговарајућа повезаност довољна да се одлучи о припадности и приказани алгоритам може да се изврши у меморијском простору .

Последице[уреди]

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

  • PSPACE = NPSPACE – ово директно следи из чињенице да је квадрат полинома и даље полином,
  • NL ⊆ L² - STCON је NL комплетан тако да сви језици који припадају NL, такође припадају класи сложености L² = .

Референце[уреди]

  1. Arora & Barak (2009) pp. 86
  2. Arora & Barak (2009) pp. 92

Литература[уреди]

Спољашње везе[уреди]