В теории сложности вычислений , теорема сэвич , доказанная Walter Савич в 1970 году, дает связь между детерминированной и недетерминистической пространством сложностью . В нем говорится, что для любой функции,
Другими словами, если недетерминированная машина Тьюринга может решить проблему, используя пространство f ( n ), обычная детерминированная машина Тьюринга может решить ту же проблему в квадрате этой границы пространства. [1] Хотя кажется, что недетерминизм может приводить к экспоненциальному выигрышу во времени, эта теорема показывает, что он имеет значительно более ограниченное влияние на требования к пространству. [2]
Доказательство
Существует конструктивное доказательство теоремы: оно демонстрирует алгоритм для STCON , проблему определения, существует ли путь между двумя вершинами в ориентированном графе , который выполняется впространство для n вершин. Основная идея алгоритма состоит в том, чтобы рекурсивно решить несколько более общую задачу, проверяя существование пути от вершины s к другой вершине t, который использует не более k ребер, где k - параметр, который задается в качестве входных данных для рекурсивного алгоритм; STCON может быть решен из этой проблемы, установив k на n . Чтобы проверить путь k- кромки от s до t , можно проверить, может ли каждая вершина u быть серединой пути, рекурсивным поиском путей половинной длины от s до u и от u до t . Используя псевдокод (с синтаксисом, очень похожим на Python ), мы можем выразить этот алгоритм следующим образом:
def k_edge_path ( s , t , k ) -> bool : "" "Теорема Сэвича." "" if k == 0 : return s == t if k == 1 : return s == t or ( s , t ) в ребрах для u в вершинах : если k_edge_path ( s , u , floor ( k / 2 )) и k_edge_path ( u , t , ceil ( k / 2 )): вернуть True вернуть False
Этот поиск вызывает себя до глубины рекурсии O (log n ) уровней, каждый из которых требует O (log n ) битов для хранения аргументов функции и локальных переменных на этом уровне, поэтому общее пространство, используемое алгоритмом, равно. Хотя описанный выше в форме программы на языке высокого уровня, тот же алгоритм может быть реализован с той же асимптотической границей пространства на машине Тьюринга .
Причина, по которой этот алгоритм подразумевает теорему, заключается в том, что любой язык соответствует ориентированному графу, вершинами которого являются конфигурации машины Тьюринга отступали членство в L . Для каждого, этот граф имеет путь от начальной конфигурации на входе x до принимающей конфигурации тогда и только тогда, когда. Таким образом, принятия решения о подключении достаточно, чтобы определить принадлежность к L , и с помощью вышеуказанного алгоритма это можно сделать в.
Следствия
Некоторые важные следствия теоремы включают:
Смотрите также
Заметки
Рекомендации
- Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность. Современный подход , Cambridge University Press , ISBN 978-0-521-42426-4, Zbl 1193,68112
- Пападимитриу, Христос (1993), «Раздел 7.3: Метод достижимости», Вычислительная сложность (1-е изд.), Аддисон Уэсли, стр. 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.
- Ричард Дж. Липтон , Теорема Сэвича . Дает исторический отчет о том, как было обнаружено доказательство.