В теории сложности вычислений , то Иммерман-Szelepcsenyi теорема утверждает , что недетерминированными пространство классы сложности закрыты под комплементарности. Это было независимо доказано Нилом Иммерманом и Робертом Селепсеньи в 1987 году, за что они разделили премию Гёделя 1995 года . В общем виде теорема утверждает, что NSPACE ( s ( n )) = co-NSPACE ( s ( n )) для любой функции s ( n ) ≥ log n . Результат эквивалентен NL= co-NL; хотя это частный случай, когда s ( n ) = log n , он подразумевает общую теорему стандартным аргументом заполнения . [1] Результат решил вторую проблему LBA .
Другими словами, если недетерминированная машина может решить проблему, другая машина с такими же ограничениями ресурсов может решить свою проблему дополнения (с обратными ответами « да» и « нет» ) в том же асимптотическом объеме пространства. Подобный результат не известен для классов временной сложности , и действительно высказывается предположение, что NP не равно co-NP .
Принцип, используемый для доказательства теоремы, стал известен как индуктивный счет . Он также использовался для доказательства других теорем о вычислительной сложности, включая закрытие LOGCFL при дополнении и существование безошибочных алгоритмов рандомизированного лог-пространства для USTCON . [2]
Доказательство эскиза
Теорема может быть доказана, показывая , как перевести любой недетерминированную машину Тьюринга M в другую недетерминированную машину Тьюринга , которая решает комплементарные задачи принятия решения в соответствии с O один и те же пространственных ограничений, а также постоянное количество указателей и счетчиков, который нуждается лишь логарифмическая величиной космос.
Идея состоит в том, чтобы смоделировать все конфигурации M и проверить, принимает ли какая-либо конфигурация. Это можно сделать в NSPACE той же величины, но для отслеживания конфигураций требуется также постоянное количество указателей и счетчиков. Если конфигурация не принимается, имитирующая машина Тьюринга принимает ввод; таким образом, он принимает тогда и только тогда, когда у M нет принимающего пути. В дальнейшем эта идея разрабатывается для логарифмического NSPACE ( NL ); обобщение на более крупный NSPACE несложно, но также может быть доказано с помощью заполнения .
Состояния M (описываемые положением его головы на входной ленте и конфигурацией рабочей памяти лог-пространства) можно рассматривать как вершины ориентированного графа , а переходы M можно рассматривать как ребра в этом графике. M принимает входную строку всякий раз, когда существует путь в этом графе от вершины s, которая представляет начальное состояние, до специальной вершины t, которая представляет любое принимающее состояние. Таким образом, существование принимающего недетерминированного вычисления для M можно рассматривать как версию проблемы st- связности для неявных графов, а не графов, заданных явно как явно представленный входной граф. В этом графическом представлении цель доказательства - найти недетерминированный алгоритм лог-пространства, который принимает только тогда, когда не существует пути от s к t в том же неявном графе.
Алгоритм, который решает эту проблему недостижимости, может быть основан на принципе подсчета для каждого числа i от 1 до n ( порядок неявного графа) числа r вершин, достижимых из s путями длины не более i. . Если на любом этапе алгоритма известно правильное значение r для некоторого значения i , то можно проверить, достижима ли данная вершина v из s путями длины не более i + 1 , используя следующие подпрограмма:
- Если v = s , вернуть истину
- Инициализировать счетчик c до 0
- Для каждой вершины u в неявном графе повторите следующие шаги:
- Недетерминированно искать путь длины не более i от s до u
- Если путь к u найден, увеличьте c и проверьте, существует ли ребро от u до v.
- Если c ≠ r , остановить алгоритм и отклонить ввод. В противном случае верните true, если было найдено ребро от u до v , и false в противном случае.
При использовании в более крупном недетерминированном алгоритме единственными приемлемыми вычислениями алгоритма могут быть те, в которых подпрограмма находит пути ко всем достижимым вершинам и вычисляет правильный ответ, поэтому эту подпрограмму можно использовать, как если бы она была детерминированной. С его помощью алгоритм проверки недостижимости t из s может быть выражен следующими шагами:
- Инициализировать i равным 0 и r равным 1
- Повторите следующие шаги n - 2 раза:
- // r = # вершин достижимых за i шагов
- Инициализировать счетчик d равным 0
- Для каждой вершины v проверьте, достижима ли v из s за i + 1 шаг, и если да, увеличьте d
- Увеличиваем i и устанавливаем r на d
- Проверьте, достижимо ли t из s в течение i + 1 шагов, и отклоните ввод, если это так.
- В противном случае, если i + 1 равно n , примите ввод.
Алгоритму нужно только поддерживать представления постоянного числа счетчиков и вершин в своей памяти, поэтому он использует логарифмическое пространство. Применяя этот алгоритм к неявному графу , построенному из данной недетерминированной машины М , получается недетерминированная машина для дополнительного языка к одному принятым М .
Иерархия пространства журнала
Как следствие, в той же статье Иммерман доказал, что, используя равенство описательной сложности между NL и FO (Transitive Closure) , логарифмическая иерархия, то есть языки, определяемые чередующейся машиной Тьюринга в логарифмическом пространстве с ограниченным числом чередований , является тем же классом, что и NL.
Смотрите также
- Теорема Савича связывает недетерминированные пространственные классы с их детерминированными аналогами.
Заметки
- ^ Стандартный справочник по заполнению в пространственной сложности (предшествующий этой теореме) - это Savitch, Walter J. (1970), «Взаимосвязь между недетерминированными и детерминированными сложностями ленты», Journal of Computer and System Sciences , 4 : 177–192, doi : 10.1016 / s0022-0000 (70) 80006-х , ЛВП : 10338.dmlcz / 120475 , МР 0266702. Для более сильного аргумента заполнения, который применяется даже к классам сложности сублогарифмического пространства, см. Szepietowski, Andrzej (1994), машины Тьюринга с сублогарифмическим пространством , Lecture Notes in Computer Science, 843 , Springer-Verlag, Berlin, doi : 10.1007 / 3-540-58355-6 , ISBN 3-540-58355-6, MR 1314820.
- ^ Бородин, Аллан ; Кук, Стивен А .; Даймонд, Патрик В .; Ruzzo, Walter L .; Tompa, Martin (1989), "Два применения индуктивного счета для задач дополнения", SIAM Journal on Computing , 18 (3): 559–578, CiteSeerX 10.1.1.394.1662 , doi : 10.1137 / 0218038.
Рекомендации
- Иммерман, Нил (1988), "Недетерминированные пространство закрыто под дополнительности" (PDF) , SIAM журнал по вычислениям , 17 (5): 935-938, DOI : 10,1137 / 0217058 , MR 0961049
- Szelepcsényi, Роберт (1987), "Метод принуждения для недетерминированных автоматов", Бюллетень EATCS , 33 : 96–100
Внешние ссылки
- Лэнс Фортноу , Основы сложности, Урок 19: Теорема Иммермана – Селепченьи . Проверено 09.09.09.