Введение
В теории вычислительной сложности, класс NL-полных задач содержит языки, являющиеся полными для класса NL, то есть для класса задач, решаемых недетерминированной машиной Тьюринга с использованием логарифмического объема памяти. Языки, полные по NL, представляют собой наиболее "сложные" или "выразительные" задачи в NL. Если существует детерминированный алгоритм для решения хотя бы одной NL-полной задачи с использованием логарифмического объема памяти, то NL = L.
Определения
NL состоит из задач, решаемых недетерминированной машиной Тьюринга с лентой ввода только для чтения и отдельной лентой для чтения-записи, размер которой ограничен пропорционально логарифму длины входных данных. Аналогично, L состоит из языков, решаемых детерминированной машиной Тьюринга при тех же ограничениях на длину ленты. Поскольку число различных конфигураций этих машин ограничено полиномиально, и L, и NL являются подмножествами класса P – детерминированных задач принятия решений за полиномиальное время. Формально, задача принятия решений является NL-полной, если она принадлежит классу NL и обладает дополнительным свойством: любая другая задача принятия решений из NL может быть сведена к ней. Если не оговорено иное, под сведением в данном определении подразумевается сведение «многие к одному» с помощью детерминированного алгоритма, использующего логарифмическое пространство.
Свойства
Если полный по NL язык X может принадлежать L, то и любой другой язык Y в NL также будет принадлежать L. Действительно, предположим (в силу NL-полноты), что существует детерминированное сведение в логарифмическом пространстве r, которое отображает экземпляр y задачи Y в экземпляр x задачи X, и также (в силу предположения, что X принадлежит L), что существует детерминированный алгоритм, работающий в логарифмическом пространстве, A для решения задачи X. При этих предположениях, задача y в языке Y может быть решена в логарифмическом пространстве алгоритмом, который моделирует поведение алгоритма A на входе r(y), используя алгоритм сведения для моделирования каждого доступа к ленте только для чтения для r(y). Из теоремы Иммермана — Селепчени следует, что если язык является ко-NL-полным (то есть, если его дополнение является NL-полным), то сам язык также является NL-полным.
Примеры
Одной из важных полных для NL задач является ST-связность (или "достижимость") (Papadimitriou 1994 Thrm. 16.2) – задача определения, существует ли путь из узла s в узел t в заданном ориентированном графе G. ST-связность можно отнести к классу NL, поскольку мы начинаем с узла s и недетерминированно переходим ко всем достижимым узлам. ST-связность является NP-трудной для NL, что можно показать, рассмотрев граф состояний вычислений любого другого алгоритма из класса NL, и учитывая, что этот алгоритм примет входные данные тогда и только тогда, когда существует (недетерминированный) путь из начального состояния в принимающее состояние. Другой важной полной для NL задачей является 2-удовлетворимость (Papadimitriou 1994 Thrm. 16.3) – задача определения, существует ли хотя бы одна такая интерпретация переменных, при которой булева формула в конъюнктивной нормальной форме, где каждое дизъюнкт содержит ровно две переменные, становится истинной. Было показано, что задача однозначной декодируемости кода переменной длины является co-NP-полной для NL. Rytter использовал вариант алгоритма Sardinas–Patterson, чтобы доказать, что дополнительная задача – поиск строки, имеющей несколько неоднозначных декодировок – принадлежит классу NL. В силу теоремы Иммермана — Селепчени, следует, что однозначная декодируемость также является NP-полной для NL. Дополнительные полные для NL задачи по пропозициональной логике, алгебре, линейным системам, графам, конечным автоматам и контекстно-свободным грамматикам перечислены в Jones (1976).