NL-полный

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

Определения

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

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

Свойства

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

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

Примеры

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

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

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

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

Ссылки

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