Теорема савичса - Savitchs theorem

В теория сложности вычислений, Теорема савича, доказано Уолтер Сэвич в 1970 г. дает связь между детерминированными и недетерминированными космическая сложность. В нем говорится, что для любой функции ${\displaystyle f\in \Omega (\log(n))}$,

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).}$

Другими словами, если недетерминированная машина Тьюринга может решить проблему с помощью ж(п) пространство, обычное детерминированная машина Тьюринга может решить ту же проблему в квадрате этой границы пространства.^[1] Хотя кажется, что недетерминизм может приводить к экспоненциальному выигрышу во времени, эта теорема показывает, что он имеет значительно более ограниченное влияние на требования к пространству.^[2]

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

Существует конструктивное доказательство теоремы: демонстрируется алгоритм для STCON, проблема определения, существует ли путь между двумя вершинами в ориентированный граф, который работает в ${\displaystyle O\left((\log n)^{2}\right)}$ место для п вершины. Основная идея алгоритма - решить рекурсивно несколько более общая проблема, проверка существования пути из вершины s в другую вершину т который использует самое большее k края, где k - параметр, который передается на вход рекурсивного алгоритма; STCON может быть решен из этой проблемы, установив k к п. Чтобы проверить k-реберный путь от s к т, можно проверить, каждая ли вершина ты может быть серединой пути путем рекурсивного поиска путей половинной длины из s к ты и ты к т.Использование псевдокода (с синтаксисом, очень похожим на Python ) мы можем выразить этот алгоритм следующим образом:

def k_edge_path(s, т, k) -> bool:    "" "Теорема Савича." ""    если k == 0:        возвращаться s == т    если k == 1:        возвращаться s == т или же (s, т) в края    за ты в вершины:        если k_edge_path(s, ты, этаж(k / 2)) и k_edge_path(ты, т, потолок(k / 2)):            возвращаться Истинный    возвращаться Ложь

Этот поиск вызывает сам себя до глубины рекурсии О(бревноп) уровни, каждый из которых требует О(бревноп) биты для хранения аргументов функции и локальные переменные на этом уровне, поэтому общее пространство, используемое алгоритмом, равно ${\displaystyle O\left((\log n)^{2}\right)}$. Хотя описанный выше в виде программы на языке высокого уровня, тот же алгоритм может быть реализован с той же асимптотической границей пространства на Машина Тьюринга.

Причина, по которой этот алгоритм подразумевает теорему, заключается в том, что любой язык ${\displaystyle L\in {\mathsf {NSPACE}}\left(f\left(n\right)\right)}$ соответствует ориентированному графу, вершинами которого являются ${\displaystyle 2^{O\left(f(n)\right)}}$ конфигурации машины Тьюринга, решающие членство в L. Для каждого ${\displaystyle x\in \{0,1\}^{n}}$, этот график имеет путь от начальной конфигурации на входе Икс к принимающей конфигурации тогда и только тогда, когда ${\displaystyle x\in L}$. Таким образом, решения о подключении достаточно, чтобы принять решение о членстве в L, и по описанному выше алгоритму это можно сделать в ${\displaystyle {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right)}$.

Следствия

Некоторые важные следствия теоремы включают:

• PSPACE = NPSPACE
  • Это непосредственно следует из того факта, что квадрат полиномиальной функции остается полиномиальной функцией. Считается, что подобная связь не существует между классами полиномиальной временной сложности, п и НП, хотя это все еще открытый вопрос.
• NL ⊆ L²
  • STCON - это NL-полный, и поэтому все языки в NL также относятся к классу сложности ${\displaystyle {\mathsf {\color {Blue}L}}^{2}={\mathsf {DSPACE}}\left(\left(\log n\right)^{2}\right)}$.

Смотрите также

• Гипотеза экспоненциального времени
• Теорема Иммермана – Селепсеньи

Примечания

1. Арора и Барак (2009) стр.86
2. Арора и Барак (2009) стр.92

Рекомендации

• Арора, Санджив; Варак, Вооз (2009), Вычислительная сложность. Современный подход, Издательство Кембриджского университета, ISBN  978-0-521-42426-4, Zbl  1193.68112
• Пападимитриу, Христос (1993), «Раздел 7.3: Метод достижимости», Вычислительная сложность (1-е изд.), Addison Wesley, стр. 149–150, ISBN  0-201-53082-1
• Сэвич, Уолтер Дж. (1970), «Отношения между недетерминированной и детерминированной сложностями ленты», Журнал компьютерных и системных наук, 4 (2): 177–192, Дои:10.1016 / S0022-0000 (70) 80006-X, HDL:10338.dmlcz / 120475
• Сипсер, Майкл (1997), "Раздел 8.1: Теорема Савича", Введение в теорию вычислений, PWS Publishing, стр.279–281, ISBN  0-534-94728-X

внешняя ссылка

• Лэнс Фортноу, Основы сложности, Урок 18: Теорема Савича. Проверено 09.09.09.
• Ричард Дж. Липтон, Теорема Савича. Дает исторический отчет о том, как было обнаружено доказательство.