Классы L, NL, coNL. NL-полнота задачи о достижимости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(NL-полнота)
Строка 28: Строка 28:
 
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.
 
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.
 
| proof =  
 
| proof =  
Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.
+
Задача <tex>CONN = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.
  
Докажем, что <tex>\mathrm{CONN} \in \mathrm{NL}</tex>.
+
Докажем, что <tex>CONN \in \mathrm{NL}</tex>.
 
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
 
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
  
Строка 43: Строка 43:
 
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <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>CONN</tex> с использованием не более чем логарифмической памяти.
  
Необходимо по данной задаче из <tex>\mathrm{NL}</tex> построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи <tex>\mathrm{CONN}</tex> для которой будет эквивалентно решению данной задачи.
+
Необходимо по данной задаче из <tex>\mathrm{NL}</tex> построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи <tex>CONN</tex> для которой будет эквивалентно решению данной задачи.
  
 
Любая машина Тьюринга, которая принимает некоторый язык <tex>\mathrm{L}</tex> из <tex>\mathrm{NL}</tex>, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.
 
Любая машина Тьюринга, которая принимает некоторый язык <tex>\mathrm{L}</tex> из <tex>\mathrm{NL}</tex>, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.
Строка 54: Строка 54:
  
 
}}
 
}}
 
 
  
 
==Теорема Иммермана==
 
==Теорема Иммермана==

Версия 01:06, 1 июня 2012

Определение:
Класс [math]L[/math] — множество языков, разрешимых на детерминированной машине Тьюринга с использованием [math]O(\log n)[/math] дополнительной памяти для входа длиной [math]n[/math]. [math]L = \mathrm{DSPACE}(O(\log n))[/math]


Определение:
Класс [math]\mathrm{NL}[/math] — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием [math]O(\log n)[/math] дополнительной памяти для входа длиной [math]n[/math]. [math]\mathrm{NL} = \mathrm{NSPACE}(O(\log n))[/math]


Определение:
Класс [math]\mathrm{coNL}[/math] — множество языков, дополнение до которых принадлежит [math]\mathrm{NL}[/math].


Теорема:
[math]\mathrm{L} \subset \mathrm{NL} \subset \mathrm{P}.[/math]
Доказательство:
[math]\triangleright[/math]

1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому [math]\mathrm{L} \in \mathrm{NL}[/math].

2. Число конфигураций машины, использующей [math]O(\log n)[/math] памяти не превышает [math]2^{O(\log n)} = n^{O(1)} = poly(n)[/math], а, следовательно, машина завершает свою работу за [math]O(poly(n))[/math] времени. Следовательно, [math]\mathrm{NL} \in \mathrm{P}.[/math]
[math]\triangleleft[/math]

NL-полнота

Определение:
Язык [math]X[/math]называют [math]\mathrm{NL}[/math]-полным, если [math]X \in \mathrm{NL}[/math] и [math]\forall Y : Y \in NL, Y \leq_L X[/math].


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

Задача [math]CONN = \{\langle G, s, t \rangle[/math] : в графе G [math]\exists [/math] путь из s в t[math]\}[/math].

Докажем, что [math]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]CONN[/math] с использованием не более чем логарифмической памяти.

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

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

Очевидно, что для любого слова из языка [math]\mathrm{L}[/math], то есть принимаемого данной машиной Тьюринга, будет существовать путь из [math] s [/math] в [math] t [/math] в построенном графе [math] G [/math]. А если для некоторого слова не из [math]\mathrm{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{coNL} = \mathrm{NL}.[/math]
Доказательство:
[math]\triangleright[/math]

Решим задачу [math]\mathrm{NCONN} = \{\langle G, s, t \rangle[/math] : в графе G нет пути из s в t[math]\}[/math]. Очевидно, что этот язык является дополнением языка [math]\mathrm{CONN}[/math]. Чтобы показать, что [math]\mathrm{NCONN}\in \mathrm{NL}[/math], придумаем недетерминированый алгоритм, использующий [math]O(\log |G|)[/math] памяти, который проверяет, достижима ли вершина [math]t[/math] из [math]s[/math].

Определим [math]R_i[/math] = {[math]v:[/math] существует путь из [math]s[/math] в [math]v[/math] длиной [math]\leq i[/math]}. Другими словами это множество всех вершин, достижимых из [math]s[/math] не более чем за [math]i[/math] шагов. Обозначим [math]|R_i|[/math] за [math]r_i[/math]. Если [math]t \notin R_{n-1}[/math], где [math]n = |V|[/math], то не существует путь из [math]s[/math] в [math]t[/math] в графе [math]G[/math], то есть [math]\langle G, s, t \rangle \in \mathrm{NCONN}[/math].

Лемма:
Можно построить недетерминированный алгоритм, который будет допускать [math]r_i[/math] и при этом будет перечислять все вершины из [math]R_i[/math] на [math]O(\log |G|)[/math] памяти.
Доказательство:
[math]\triangleright[/math]

Можно построить недетерминированный алгоритм, который будет допускать [math]r_i[/math] и при этом будет перечислять все вершины из [math]R_i[/math] на [math]O(\log |G|)[/math] памяти.

   Enum([math]s, i, ri, G[/math])
   [math]counter[/math] [math]\leftarrow[/math] 0                 //количество уже найденных и выведенных элементов
   for [math]v = 1..n[/math] do              //перебираем все вершины графа
       continue or find path      //недетерминированно угадываем путь из s до v или переходим к следующей вершине
       [math]counter[/math]++
       return' [math]v[/math]                //выдаем вершину, до которой угадали путь
   if ([math]counter \geq r_i[/math])             //нашли [math]r_i[/math] вершин, допускаем, завершаем работу
       accept
   reject                  //не нашли [math]r_i[/math] вершин, не допускаем
   

Enum перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из [math]s[/math]. Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из [math]s[/math] в [math]v[/math]. Для угадывания пути необходимо [math]O(\log |G|)[/math] памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. Enum является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий accept, то происходит допуск.

Теперь, имея Enum, можно по индукции находить [math]r_i[/math]. Очевидно, что [math]r_0 = 1[/math], так как [math]R_0[/math] содержит единственную вершину — [math]s[/math]. Пусть известно значение [math]r_i[/math]. Напишем программу, которая на логарифмической памяти будет находить [math]r_{i + 1}[/math].


 Next([math]s, i, r_i, G[/math])
   [math]r = 1[/math]                              //[math]r_{i+1}[/math] хотя бы один, так как [math]r \in R_{i+1}[/math]
   for [math]v = 1..n[/math]; [math]v \ne s[/math] do               //перебираем все вершины графа, кроме [math]s[/math] — это кандидаты на попадание в [math]R_{i+1}[/math]
     for [math]u : (u, v) \in E[/math] do               //перебираем все ребра, входящие в [math]v[/math]
       if ([math]u[/math] in Enum([math]s, i, r_i, G[/math]))   //перечисляем все вершины из [math]R_i[/math], если [math]u[/math] одна из них, то [math]v \in R_{i+1}[/math]
         [math]r[/math]++                            //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата
         break 
   return [math]r[/math]


Данный алгоритм изначально учитывает [math]s[/math], а затем перебирает всех возможных кандидатов [math]v[/math] на попадание в [math]R_{i + 1}[/math]. Для каждого из них перебираются все ребра, в него входящие. Затем перечисляются все вершины из [math]R_i[/math] и, если начало нашего ребра было перечислено, то [math]v \in R_{i + 1}[/math]. Алгоритм использует [math]O(\log |G|)[/math] памяти, так необходимо хранить лишь [math]v[/math], [math]u[/math], [math]r[/math] и еще поочередно значения полученные в результате вызова Enum.

Теперь напишем алгоритм, который будет недетерминированно решать задачу [math]\mathrm{NCONN}[/math] на логарифмической памяти. Он будет состоять из двух частей: вычисление [math]r_{n-1}[/math] и перечисление всех вершин из [math]R_{n - 1}[/math]. Вычисление [math]r_{n-1}[/math] происходит путем вызова Next [math]n - 1[/math] раз, при этом каждый раз в качестве [math]r_i[/math] подставляется новое полученное значение.


 NCONN([math]G, s, t[/math])
   [math]r_n = 1[/math]                             //[math]r_0 = 1[/math]
   for [math]i = 0..n - 2[/math] do                //вычисляем [math]r_{n-1}[/math]
     [math]r_n = [/math] Next([math]s, i, r_n, G[/math])
   if ([math]t1[/math] in Enum([math]s, n - 1, r_n, G[/math]))   //перечисляем вершины из [math]R_{n-1}[/math], если [math]t[/math] была перечислена, то [math]t[/math] достижима и выдаем reject, иначе accept
     reject
   else
     accept

Данный алгоритм использует [math]O(\log |G|)[/math] памяти, так как для хранения [math]r_n[/math] и [math]i[/math] необходимо [math]O(\log |G|)[/math], и для вызываемых Next и Enum необходимо [math]O(\log |G|)[/math] памяти.

Таким образом показано, что [math]\mathrm{NCONN} \in \mathrm{NL}[/math]. Поскольку [math]\mathrm{CONN} \in \mathrm{NLC}[/math], то аналогичным образом [math]\mathrm{NCONN} \in \mathrm{coNLC}[/math]. Получаем, что любую задачу из [math]\mathrm{coNL}[/math] можно свести к задаче из [math]\mathrm{NL}[/math], а значит [math]\mathrm{coNL} \subset \mathrm{NL}[/math].

Из соображений симметрии [math]\mathrm{NL} \subset \mathrm{coNL}[/math], а значит [math]\mathrm{coNL} = \mathrm{NL}[/math].
[math]\triangleleft[/math]
[math]\triangleleft[/math]