NL-полнота задачи о достижимости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
{{ Определение
 
{{ Определение
 
|definition=Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G есть путь из s в t<tex>\}</tex> {{---}} задача существования пути между двумя заданными вершинами в данном графе.
 
|definition=Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G есть путь из s в t<tex>\}</tex> {{---}} задача существования пути между двумя заданными вершинами в данном графе.

Версия 09:08, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

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


Определение:
Задача [math]\mathrm{CONN} = \{\langle G, s, t \rangle \bigm|[/math] в графе G есть путь из s в t[math]\}[/math] — задача существования пути между двумя заданными вершинами в данном графе.


Теорема:
Задача существования пути между двумя заданными вершинами в данном графе NL-полна относительно [math]\mathrm{\widetilde{L}}[/math]-сведения.
Доказательство:
[math]\triangleright[/math]

Докажем, что [math]\mathrm{CONN} \in \mathrm{NL}[/math]. Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает [math] O(\log n) [/math] памяти, где [math] n [/math] — размер входа, и за время порядка [math] O(poly(n)) [/math] решает эту задачу.

Алгоритм:

  1. Начиная с вершины [math] s [/math] недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных).
  2. Проверяем, правда ли, что текущая вершина совпадает с [math] t [/math]. Если это так, возвращает TRUE.
  3. Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.

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

Теперь докажем, что любая задача из класса [math]\mathrm{NL}[/math] сводится к задаче [math]\mathrm{CONN}[/math] с использованием не более чем логарифмической памяти.

Необходимо по данной задаче из [math]\mathrm{NL}[/math] построить тройку [math] \langle G, s, t \rangle [/math], решение задачи [math]\mathrm{CONN}[/math] для которой будет эквивалентно решению данной задачи.

Любая машина Тьюринга, которая принимает некоторый язык [math]L[/math] из [math]\mathrm{NL}[/math], использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга [math] O(poly(n)) [/math]. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в [math] G [/math], а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) — ребро в графе [math] G [/math]. За вершину [math] s [/math] принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину [math] t [/math].

Очевидно, что для любого слова из языка [math]L[/math], то есть принимаемого данной машиной Тьюринга, будет существовать путь из [math] s [/math] в [math] t [/math] в построенном графе [math] G [/math]. А если для некоторого слова не из [math]L[/math] в [math] G [/math] существует путь из [math] s [/math] в [math] t [/math], то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.

Такое построение графа [math] G [/math] по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их [math] O(poly(n)) [/math], потому переменная, перебирающая его занимает [math] O(\log n) [/math] памяти), переходов из него и проверки возможности перехода.
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{NL} \subseteq \mathrm{P}[/math] (следствие из предыдущей теоремы).
Доказательство:
[math]\triangleright[/math]

Необходимо доказать, что [math]\forall \mathrm{B} \in \mathrm{NL}[/math] верно, что [math]\mathrm{B} \in \mathrm{P}[/math].

По определению [math]\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL} [/math] и [math]\forall \mathrm{B} \in \mathrm{NL} [/math] верно, что [math]\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}[/math]. Следовательно, если [math]\exists \mathrm{A} \in \mathrm{NLC} : \mathrm{A} \in \mathrm{P}[/math], то [math]\forall \mathrm{B}[/math], сводимого к [math]\mathrm{A}[/math] верно, что [math]\mathrm{B} \leq_{\widetilde{P}} \mathrm{A}[/math], следовательно, поскольку класс [math]\mathrm{P}[/math] замкнут относительно [math]\widetilde{\mathrm{P}}[/math]-сведения по Карпу, [math]\mathrm{B} \in \mathrm{P}[/math]. Таким образом, если существует язык, принадлежащий [math]\mathrm{NLC}[/math] и [math]\mathrm{P}[/math], то теорема доказана. Как было показано выше, [math]\mathrm{CONN} \in \mathrm{NLC}[/math]. [math]\mathrm{CONN} \in \mathrm{P}[/math], что очевидно следует из существования алгоритма DFS.
[math]\triangleleft[/math]