WikiDer > NL-полный

NL-complete

В теория сложности вычислений, NL-полный это класс сложности содержащие языки, которые полный за NL, класс проблемы решения это может быть решено недетерминированная машина Тьюринга с помощью логарифмический объем памяти. NL-полные языки - самые "сложные" или "выразительные" проблемы в NL. Если существует метод решения какой-либо одной из NL-полных задач в логарифмической памяти, то NL = L.

Определения

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

Формально проблема решения является NL-полным, когда он принадлежит NL, и обладает дополнительным свойством, присущим любой другой проблеме решения в NL возможно уменьшенный к нему. Если не указано иное, сокращения в этом определении предполагаются сокращениями "многие-единицы" с помощью детерминированного алгоритма логарифмического пространства.

Характеристики

Если NL-полный язык Икс может принадлежать L, то и любой другой язык Y в NL. В самом деле, предположим (по NL-полноте), что существует детерминированное сокращение лог-пространства р который отображает экземпляр у проблемы Y к экземпляру Икс проблемы Икс, а также (в предположении, что Икс в L), что существует детерминированный алгоритм лог-пространства А для решения проблемы Икс. С этими предположениями проблема у на языке Y может быть решена в логарифмическом пространстве с помощью алгоритма, который имитирует поведение алгоритма А на входе р(у), используя алгоритм сокращения для моделирования каждого доступа к ленте только для чтения для р(у).

Это следует из Теорема Иммермана – Селепсеньи что, если язык является co-NL-полным (то есть, если его дополнять является NL-полным), то сам язык также является NL-полным.

Примеры

Одна из важных проблем NL-complete: ST-подключение (или «достижимость») (Papadimitriou 1994 Thrm. 16.2), проблема определения того, является ли заданный ориентированный граф грамм и два узла s и т на этом графе есть путь из s к т. ST-соединение можно увидеть в NL, потому что мы начинаем с узла s и недетерминированно перейти к каждому другому достижимому узлу. ST-связность можно увидеть как NL-сложную, рассматривая граф состояний вычислений любого другого NL алгоритм, и учитывая, что другой алгоритм будет принимать, если и только если существует (недетермический) путь от начального состояния до принимающего состояния.

Еще одна важная проблема NL-complete: 2-выполнимость (Papadimitriou 1994 Thrm. 16.3), проблема определения того, является ли логическая формула в конъюнктивная нормальная форма с двумя переменными в каждом предложении.

Проблема однозначной дешифрируемости данного код переменной длины было показано, что он является co-NL-полным Риттер (1986); Риттер использовал вариант Алгоритм Сардин-Паттерсона чтобы показать, что дополнительная проблема, поиск строки, которая имеет несколько неоднозначных декодирований, принадлежит NL. Из теоремы Иммермана – Селепсеньи следует, что однозначная дешифрируемость также является NL-полной.

Дополнительные задачи NL-complete на Логика высказываний, Алгебра, линейная система, график, Конечные автоматы, Контекстно-свободная грамматика перечислены в Jones (1976).

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

  • Пападимитриу, Христос Х. (1994). Вычислительная сложность. Ридинг, Массачусетс: Эддисон-Уэсли. ISBN 0-201-53082-1.
  • Риттер, Войцех (1986), "Пространственная сложность проблемы однозначной дешифрируемости", Письма об обработке информации, 23 (1): 1–3, Дои:10.1016/0020-0190(86)90121-3, МИСТЕР 0853618.
  • Джонс, Нил Д.; Льен, Ю. Эдмунд; Лаазер, Уильям Т (1976). «Новые задачи завершены для недетерминированного журнального пространства». Математическая теория систем. 10 (1): 1–17. Дои:10.1007 / BF01683259.