NL-полнота

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

В классе 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) памяти. Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции (который запрашивает детерминированная машина Тьюринга, соответствующая языку [math]A[/math], для определения истинности [math]f(x) \in A[/math]) будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата.

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

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

2-SAT