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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 10 промежуточных версий этого же участника)
Строка 2: Строка 2:
  
 
{{ Определение
 
{{ Определение
|definition=<tex>\mathrm{A} \in \mathrm{PC} \Leftrightarrow \mathrm{A} \in \mathrm{P}</tex> и <tex>\forall \mathrm{B} \in \mathrm{P} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>.
+
|definition=<tex>\mathrm{A} \in \mathrm{P}</tex>-complete <tex>\Leftrightarrow \mathrm{A} \in \mathrm{P}</tex> и <tex>\forall \mathrm{B} \in \mathrm{P} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>.
 
}}
 
}}
  
 
{{ Определение
 
{{ Определение
 
|definition=<tex>\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL}</tex> и <tex>\forall \mathrm{B} \in \mathrm{NL} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>.
 
|definition=<tex>\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL}</tex> и <tex>\forall \mathrm{B} \in \mathrm{NL} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>.
 +
}}
 +
 +
{{ Теорема
 +
| statement = <tex>\mathrm{A} \leq_{\widetilde{L}} \mathrm{B}</tex> и <tex>\mathrm{B} \in \mathrm{L} \Rightarrow \mathrm{A} \in \mathrm{L}</tex>.
 +
| proof = По определению <tex>\mathrm{\widetilde{L}}</tex>-сводимости <tex>\exists f \in \widetilde{L} : x \in \mathrm{A} \Leftrightarrow f(x) \in \mathrm{B}</tex>. Просто выполнить <tex>f(x)</tex> и передать результат в качестве ввода МТ для <tex>\mathrm{B}</tex> нельзя, так как для этого требуется <tex>\Omega(n)</tex> дополнительной памяти. Поэтому будем хранить только позицию  <tex>i</tex> головки МТ для  <tex>\mathrm{B}</tex> на входной ленте (в двоичной записи это требует <tex>O(\log n)</tex> памяти), и вычислять <tex>i</tex>-ый бит  <tex>f(x)</tex> при необходимости обращения к нему путём исполнения  <tex>f(x)</tex> без записи результата целиком. Таким образом построим МТ для <tex>\mathrm{A}</tex>, удовлетворяющую определению.
 
}}
 
}}
  
Строка 17: Строка 22:
 
| proof =  
 
| proof =  
 
Докажем, что <tex>\mathrm{CONN} \in \mathrm{NL}</tex>.
 
Докажем, что <tex>\mathrm{CONN} \in \mathrm{NL}</tex>.
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> — размер входа, и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
+
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует <tex> O(1) </tex> переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> — размер входа, и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
  
 
Алгоритм:
 
Алгоритм:
  
#Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных).
+
#Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо <tex> O(1) </tex> переменных).
#Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает TRUE.
+
#Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращаем TRUE.
#Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.
+
#Отдельно считаем количество пройденных вершин. Как только это число превысило количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.
  
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
+
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
  
 
Теперь докажем, что любая задача из класса <tex>\mathrm{NL}</tex> сводится к задаче <tex>\mathrm{CONN}</tex> с использованием не более чем логарифмической памяти.
 
Теперь докажем, что любая задача из класса <tex>\mathrm{NL}</tex> сводится к задаче <tex>\mathrm{CONN}</tex> с использованием не более чем логарифмической памяти.
Строка 35: Строка 40:
 
Очевидно, что для любого слова из языка <tex>L</tex>, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из <tex>L</tex> в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.
 
Очевидно, что для любого слова из языка <tex>L</tex>, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из <tex>L</tex> в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.
  
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходов из него и проверки возможности перехода.
+
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием <tex> O(1) </tex> переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходов из него и проверки возможности перехода.
  
 
}}
 
}}

Версия 18:05, 14 марта 2013

В классах, являющихся подмножествами [math]\mathrm{P}[/math], не используют [math]\mathrm{\widetilde{P}}[/math]-сведение по Карпу, так как оно оказывается бесполезным. Для них применяется [math]\mathrm{\widetilde{L}}[/math]-сведение (с [math]O(\log n)[/math] дополнительной памяти).


Определение:
[math]\mathrm{A} \in \mathrm{P}[/math]-complete [math]\Leftrightarrow \mathrm{A} \in \mathrm{P}[/math] и [math]\forall \mathrm{B} \in \mathrm{P} [/math] верно, что [math]\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}[/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]\mathrm{A} \leq_{\widetilde{L}} \mathrm{B}[/math] и [math]\mathrm{B} \in \mathrm{L} \Rightarrow \mathrm{A} \in \mathrm{L}[/math].
Доказательство:
[math]\triangleright[/math]
По определению [math]\mathrm{\widetilde{L}}[/math]-сводимости [math]\exists f \in \widetilde{L} : x \in \mathrm{A} \Leftrightarrow f(x) \in \mathrm{B}[/math]. Просто выполнить [math]f(x)[/math] и передать результат в качестве ввода МТ для [math]\mathrm{B}[/math] нельзя, так как для этого требуется [math]\Omega(n)[/math] дополнительной памяти. Поэтому будем хранить только позицию [math]i[/math] головки МТ для [math]\mathrm{B}[/math] на входной ленте (в двоичной записи это требует [math]O(\log n)[/math] памяти), и вычислять [math]i[/math]-ый бит [math]f(x)[/math] при необходимости обращения к нему путём исполнения [math]f(x)[/math] без записи результата целиком. Таким образом построим МТ для [math]\mathrm{A}[/math], удовлетворяющую определению.
[math]\triangleleft[/math]


Определение:
Задача [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(1) [/math] переменных, каждая из которых занимает [math] O(\log n) [/math] памяти, где [math] n [/math] — размер входа, и за время порядка [math] O(poly(n)) [/math] решает эту задачу.

Алгоритм:

  1. Начиная с вершины [math] s [/math] недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо [math] O(1) [/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(1) [/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]