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

В теории сложности вычислений , то Иммерман-Szelepcsenyi теорема утверждает , что недетерминированными пространство классы сложности закрыты под комплементарности. Это было независимо доказано Нилом Иммерманом и Робертом Селепсеньи в 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 в другую недетерминированную машину Тьюринга, которая решает проблему дополнительного решения при той же (асимптотической) пространственной сложности, плюс постоянное количество указателей и счетчиков, которое требует только логарифмического количества пространства.

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

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

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

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

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

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

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

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

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

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

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

Заметки

Рекомендации

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