NL-полнота

В классе NL выделяют подкласс полных в этом классе задач.

Определение

Язык [math]A[/math] является NL-полным (NLC), если он принадлежит классу NL и любой другой язык [math]A'[/math] из NL можно свести по Карпу к [math]A[/math], притом сведение будет использовать логарифмическое количество памяти. То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.

Теорема

Если в классе L существует такой язык [math]A[/math], что он NL-полон, то NL = L.

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

Рассмотрим язык [math]B[/math] из класса NL. Для каждого слова [math]x[/math] необходимо определять его принадлежность [math]B[/math] используя лишь детерминированные выборы и O(log n) дополнительной памяти.

Так как [math]A[/math] NL-полон, то существует такая функция [math]f[/math] (использующая O(log n) дополнительной памяти), что [math]x \in B \Leftrightarrow f(x) \in A[/math]. [math]A[/math] принадлежит L, поэтому мы можем определить принадлежность [math]x[/math] языку [math]B[/math] с необходимыми условиями.

Однако, результат работы функции [math]f[/math] сохранить невозможно, так как он может занимать более O(log n) памяти. Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата.

Примеры NL-полных задач

NL-полнота задачи о достижимости в графе

2-SAT