Войти
В теории сложности вычислений, теорема Иммермана – Селепсеньи утверждает, что недетерминированное пространство классы сложности замкнуты при дополнении. Это было независимо доказано Нилом Иммерманом и Робертом Селепсеньи в 1987 году, за что они разделили премию Гёделя 1995 года. В общем виде теорема утверждает, что NSPACE (s (n)) = co-NSPACE (s (n)) для любой функции s (n) ≥ log n. Результат эквивалентно указан как NL = co-NL; хотя это частный случай, когда s (n) = log n, он подразумевает общую теорему стандартным аргументом заполнения . Результат решил вторую проблему LBA.
Другими словами, если недетерминированная машина может решить проблему, другая машина с такими же ограничениями ресурсов может решить ее проблему дополнить (с помощью да и нет ответы перевернуты) в том же асимптотическом количестве места. Для классов временной сложности не известен аналогичный результат, и действительно высказывается предположение, что NP не равно co-NP.
. Принцип, используемый для доказательства теоремы, стал известен как. Он также использовался для доказательства других теорем о вычислительной сложности, включая закрытие LOGCFL при дополнении и существование безошибочных алгоритмов рандомизированного лог-пространства для USTCON.
Теорема может быть доказана, показывая, как переводить любую недетерминированную машину Тьюринга M в другую недетерминированную машину Тьюринга, которая решает дополнительную проблему принятия решений при O тех же ограничений по пространству, плюс постоянное количество указателей и счетчиков, для которого требуется только логарифмический количество места.
Идея состоит в том, чтобы смоделировать все конфигурации M и проверить, принимает ли какая-либо конфигурация. Это можно сделать в NSPACE той же величины, но для отслеживания конфигураций требуется также постоянное количество указателей и счетчиков. Если никакая конфигурация не принимается, имитирующая машина Тьюринга принимает ввод; таким образом, он принимает тогда и только тогда, когда у M нет принимающего пути. Эта идея подробно рассматривается ниже для логарифмического NSPACE (NL ); обобщение на более крупный NSPACE несложно, но также может быть доказано с помощью padding.
Состояния M (описываемые положением его головки на входной ленте и конфигурацией рабочей памяти пространства журнала) можно рассматривать of как вершины ориентированного графа, а переходы M можно рассматривать как ребра в этом графе. M принимает входную строку всякий раз, когда существует путь в этом графе от вершины s, которая представляет начальное состояние, до специальной вершины t, которая представляет любое принимающее состояние. Таким образом, существование принимающего недетерминированного вычисления для M можно рассматривать как версию проблемы st-связности для неявных графов, а не графов, заданных явно как явно - представлен входной граф. В этом графическом представлении цель доказательства состоит в том, чтобы найти недетерминированный алгоритм лог-пространства, который принимает только тогда, когда не существует пути от s к t в том же неявном графе.
Алгоритм, который решает эту проблему недоступности, может быть основан на принципе подсчета для каждого числа i от 1 до n (порядок неявного графа) числа r вершин, достижимых из s по пути длиной не более i. Если на любом этапе алгоритма известно правильное значение r для некоторого значения i, то можно проверить, достижима ли данная вершина v из s путями длины не более i + 1, используя следующие подпрограмма:
При использовании в более крупном недетерминированном алгоритме единственными допустимыми вычислениями алгоритма могут быть те, в которых подпрограмма находит пути ко всем достижимым вершинам и вычисляет правильный ответ, поэтому эту подпрограмму можно использовать, как если бы она была детерминированной. Имея его в руках, алгоритм проверки недостижимости t из s может быть выражен следующими шагами:
Алгоритму нужно только поддерживать представления постоянного числа счетчиков и вершин в своей памяти, поэтому он использует логарифмическое пространство. Применяя этот алгоритм к неявному графу, построенному из заданной недетерминированной машины M, можно получить недетерминированную машину для дополнительного языка к тому, который принят M.
Как следствие, в той же статье Иммерман доказал, что, используя равенство описательной сложности между NL и FO (Transitive Closure), логарифмическая иерархия, т.е. с помощью чередующейся машины Тьюринга в логарифмическом пространстве с ограниченным числом чередований является тем же классом, что и NL.
