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

Связь между детерминированной и недетерминированной сложностью пространства

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

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

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

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

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

def  stcon ( s ,  t )  ->  bool : """Проверка существования пути любой длины от s до t""" return k_edge_path ( s , t , n ) # n — количество вершин      def  k_edge_path ( s ,  t ,  k )  ->  bool : """Проверка существования пути длиной не более k из s в t""" if k == 0 : return s == t if k == 1 : return ( s , t ) in sides 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                                      

Поскольку каждый рекурсивный вызов делит параметр пополам , число уровней рекурсии равно . Каждый уровень требует бит памяти для своих аргументов функции и локальных переменных : а вершины , , и требуют бит каждая. Общая сложность вспомогательного пространства, таким образом, равна . Входной граф считается представленным в отдельной памяти только для чтения и не вносит вклад в эту границу вспомогательного пространства. В качестве альтернативы он может быть представлен как неявный граф . Хотя выше он описан в виде программы на языке высокого уровня, тот же алгоритм может быть реализован с той же асимптотической границей пространства на машине Тьюринга . ${\displaystyle k}$ ${\displaystyle \lceil \log _{2}n\rceil }$ ${\displaystyle O(\log n)}$ ${\displaystyle k}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle \lceil \log _{2}n\rceil }$ ${\displaystyle O\left((\log n)^{2}\right)}$

Этот алгоритм может быть применен к неявному графу, вершины которого представляют конфигурации недетерминированной машины Тьюринга и ее ленты, работающей в заданном ограниченном пространстве . Ребра этого графа представляют недетерминированные переходы машины, устанавливаются в начальную конфигурацию машины и устанавливаются в специальную вершину, представляющую все принимающие состояния остановки. В этом случае алгоритм возвращает true, когда машина имеет недетерминированный принимающий путь, и false в противном случае. Количество конфигураций в этом графе равно , из чего следует, что применение алгоритма к этому неявному графу использует пространство . Таким образом, определяя связность в графе, представляющем недетерминированные конфигурации машины Тьюринга, можно определить принадлежность к языку, распознаваемому этой машиной, в пространстве, пропорциональном квадрату пространства, используемого машиной Тьюринга. ${\displaystyle f(n)}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle O(2^{f(n)})}$ ${\displaystyle O(f(n)^{2})}$

Следствия

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

PSPACE = NPSPACE

То есть, языки, которые могут быть распознаны детерминированными полиномиальными машинами Тьюринга и недетерминированными полиномиальными машинами Тьюринга, одинаковы. Это следует непосредственно из того факта, что квадрат полиномиальной функции все еще является полиномиальной функцией. Считается, что аналогичной связи не существует между классами полиномиальной временной сложности P и NP , хотя это все еще открытый вопрос .

НЛ ⊆ Л2​

То есть, все языки, которые можно решить недетерминированно в логарифмическом пространстве, можно решить детерминированно в классе сложности Это следует из того факта, что STCON является NL-полным . $${\displaystyle {\mathsf {\color {Blue}L}}^{2}={\mathsf {DSPACE}}\left(\left(\log n\right)^{2}\right).}$$

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

• Теорема Иммермана–Селепченьи  – Замыкание недетерминированного пространства при дополнении

Ссылки

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

Источники

• Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность. Современный подход , Cambridge University Press , ISBN 978-0-521-42426-4, Збл  1193.68112
• Пападимитриу, Христос (1993), «Раздел 7.3: Метод достижимости», Computational Complexity (1-е изд.), Addison Wesley, стр. 149–150, ISBN 0-201-53082-1
• Сэвич, Уолтер Дж. (1970). «Связь между недетерминированными и детерминированными сложностями лент». Журнал компьютерных и системных наук . 4 (2): 177–192. doi :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.
• Ричард Дж. Липтон , Теорема Сэвича . Дает исторический отчет о том, как было обнаружено доказательство.