NL-полнота

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

Определение

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

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

Теорема

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

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

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

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

Используя логарифмическое количество памяти B сводится к языку A, который уже лежит в L.

Тонкость состоит в том, что мы не можем сохранить

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

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