Теорема Сэвича

Теорема Сэвича (1970):

NSPACE(f(n)) ⊆ DSPACE(f²(n)).

То есть, если недетерминированная машина Тьюринга может решить проблему используя f(n) памяти, то детерминированная машина Тьюринга сможет это сделать за квадрат памяти.

СледствияПравить

• PSPACE = NPSPACE
• NL ⊆ L²

Практическое применениеПравить

• Одним из примеров практического применения Теоремы Сэвича является технология “Space-time tradeoff” - "выбор оптимального соотношения памяти и времени".

Доказательство:

Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию  можно закодировать так: закодировать позицию и содержание рабочей ленты (займет  памяти), позицию входной ленты (займет  памяти). Так как , то размер конфигурации составит . Пусть . Тогда существует недетерминированная машина Тьюринга, распознающая этот язык. Рассмотрим вспомогательную функцию , вычисляющую возможность перехода из конфигурации  в конфигурацию  за не более, чем  переходов: Reach(I, J, k): if (k = 0) return (I J) or (I = J) // запись (I J) означает возможность перехода МТ из конфигурации I в конфигурацию J за один шаг else for (Y) // перебор промежуточных конфигураций if Reach(I, Y, k-1) and Reach(Y, J, k-1) return true return false Эта функция имеет глубину рекурсии , на каждом уровне рекурсии использует  памяти для хранения текущих конфигураций. Рассмотрим машину Тьюринга , распознающую язык . Эта машина может иметь  конфигураций. Объясняется это следующим образом. Пусть  имеет  состояний и  символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте . Головка на входной ленте может быть в одной из  позиций и в одной из  на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает . Рассмотрим функцию, которая по заданному слову  проверяет его принадлежность языку : Check(x, L): for (T) // перебор конфигураций, которые содержат допускающие состояния if Reach(S, T, ) return true return false Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции . И если слово не допускается за  шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено. В итоге функция  имеет глубину рекурсии , на каждом уровне рекурсии используется  памяти. Тогда всего эта функция использует  памяти.

ЛитератураПравить

• Michael Sipser  (англ.) (рус.. Introduction to the Theory of Computation (англ.). — PWS Publishing, 1997. Section 8.1: Savitch’s Theorem, pp.279-281.
• Christos Papadimitriou. Computational Complexity (неопр.). — 1st edition. — Addison Wesley, 1993. Pages 149—150 of section 7.3: The Reachability Method.
• W.J.Savitch, «Relationship between nondeterministic and deterministic tape classes», J.CSS, 4, pp 177—192, 1970