Теорема Иммермана – Селепсеньи - Immerman–Szelepcsényi theorem

В теория сложности вычислений, то Теорема Иммермана – Селепсеньи утверждает, что недетерминированное пространство классы сложности закрыты на дополнения. Это было независимо доказано Нил Иммерман и Роберт Селепсеньи в 1987 году, за который они разделили 1995 год. Премия Гёделя. В общем виде теорема утверждает, что NSPACE (s(п)) = co-NSPACE (s(п)) для любой функции s(п) ≥ журналп. Результат эквивалентно формулируется как NL = co-NL; хотя это частный случай, когда s(п) = журнал п, из него стандартным образом следует общая теорема. аргумент заполнения.[1] Результат решил вторая проблема LBA.

Другими словами, если недетерминированная машина может решить проблему, другая машина с теми же ограничениями ресурсов может решить ее. дополнять проблема (с да и нет ответы перевернуты) в том же асимптотическом количестве места. Для классов временной сложности не известен аналогичный результат, и действительно предполагается, что НП не равно со-НП.

Принцип, использованный для доказательства теоремы, стал известен как индуктивный счет. Он также использовался для доказательства других теорем о вычислительной сложности, включая замыкание LOGCFL при дополнении и существовании безошибочных алгоритмов рандомизированного лог-пространства для USTCON.[2]

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

Теорема может быть доказана, если показать, как преобразовать любую недетерминированную машину Тьюринга M в другую недетерминированную машину Тьюринга, которая решает дополнительные проблема решения под О тех же ограничений по пространству, плюс постоянное количество указателей и счетчиков, для которых требуется только логарифмический количество места.

Идея состоит в том, чтобы смоделировать все конфигурации Mи проверить, принимает ли какая-либо конфигурация. Это можно сделать в NSPACE такой же величины, но требует также постоянного количества указателей и счетчиков для отслеживания конфигураций. Если никакая конфигурация не принимается, имитирующая машина Тьюринга принимает ввод; таким образом, он принимает тогда и только тогда, когда у M нет принимающего пути. Эта идея развивается ниже для логарифмического NSPACE (NL ); обобщение на более крупный NSPACE несложно, но также может быть доказано набивка.

Состояния M (описываемый положением его головки на входной ленте и конфигурацией рабочей памяти лог-пространства) можно рассматривать как вершины ориентированный граф, а переходы M можно рассматривать как ребра в этом графе. M принимает входную строку всякий раз, когда существует путь в этом графе из вершины s который представляет начальное состояние для специальной вершины т который представляет любое принимающее состояние. Таким образом, существование приемлемого недетерминированного вычисления для M можно рассматривать как версию ул-соединение проблема, для неявные графы а не графики, заданные явно как явно представленный входной граф. В этом графическом представлении цель доказательства - найти алгоритм недетерминированного лог-пространства, который принимает только тогда, когда не существует путь от s к т в том же неявном графе.

Алгоритм, который решает эту проблему недоступности, может быть основан на принципе подсчета для каждого числа я от 1 до п (порядок неявного графа), число р вершин достижимых из s путями длиной не более я. Если на любом этапе алгоритма правильное значение р известен некоторой стоимостью я, то можно проверить, действительно ли данная вершина v доступен из s путями длиной не более я + 1, используя следующую подпрограмму:

  1. Если v = s, вернуть истину
  2. Инициализировать счетчик c до 0
  3. Для каждой вершины ты в неявном графе повторите следующие шаги:
    • Недетерминированно искать путь длиной не более я от s к ты
    • Если путь к ты найдено, приращение c и проверьте, существует ли ребро из ты к v
  4. Если c ≠ р, остановите алгоритм и отклоните ввод. В противном случае вернуть истину, если ребро из ты к v был найден, иначе - false.

При использовании в более крупном недетерминированном алгоритме единственными приемлемыми вычислениями алгоритма могут быть те, в которых подпрограмма находит пути ко всем достижимым вершинам и вычисляет правильный ответ, поэтому эту подпрограмму можно использовать, как если бы она была детерминированной. С его помощью алгоритм проверки недостижимости т от s можно выразить следующими шагами:

  1. Инициализировать я до 0 и р к 1
  2. Повторите следующие шаги п − 2 раз:
    • // р= # вершина достижима в пределах я шаги
    • Инициализировать счетчик d до 0
    • Для каждой вершины v проверить, действительно ли v доступен из s в пределах я + 1 шаги, и если да, увеличивайте d
    • Приращение я и установить р к d
  3. Проверить, действительно ли т доступен из s в пределах я + 1 шаги, и отклоните ввод, если это так.
  4. В противном случае, если я + 1 равно п, примите ввод.

Алгоритму необходимо только поддерживать представления постоянного числа счетчиков и вершин в своей памяти, поэтому он использует логарифмическое пространство. Применяя этот алгоритм к неявному графу, построенному на данной недетерминированной машине M, получается недетерминированная машина для дополнительного языка к тому, который принят M.

Иерархия пространства журнала

Как следствие, в той же статье Иммерман доказал, что, используя описательная сложность равенство между NL и FO (переходное закрытие), логарифмическая иерархия, то есть языки, определяемые переменная машина Тьюринга в логарифмическом пространстве с ограниченным числом чередований - это тот же класс, что и NL.

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

  • Теорема савича связывает недетерминированные пространственные классы с их детерминированными аналогами

Заметки

  1. ^ Стандартный справочник по заполнению пространственной сложности (предшествующий этой теореме): Савич, Уолтер Дж. (1970), "Отношения между недетерминированными и детерминированными сложностями ленты", Журнал компьютерных и системных наук, 4: 177–192, Дои:10.1016 / с0022-0000 (70) 80006-х, HDL:10338.dmlcz / 120475, Г-Н  0266702. Для более сильного аргумента заполнения, который применяется даже к классам сложности сублогарифмического пространства, см. Шепетовски, Анджей (1994), Машины Тьюринга с сублогарифмическим пространством, Конспект лекций по информатике, 843, Springer-Verlag, Берлин, Дои:10.1007/3-540-58355-6, ISBN  3-540-58355-6, Г-Н  1314820.
  2. ^ Бородин, Аллан; Кук, Стивен А.; Даймонд, Патрик В .; Ruzzo, Walter L .; Томпа, Мартин (1989), "Два применения индуктивного счета для задач дополнения", SIAM Журнал по вычислениям, 18 (3): 559–578, CiteSeerX  10.1.1.394.1662, Дои:10.1137/0218038.

использованная литература

внешние ссылки