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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Иммермана)
(Теорема Иммермана)
Строка 67: Строка 67:
 
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.
 
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.
 
Обозначим <tex>|R_i|</tex> за <tex>r_i</tex>.
 
Обозначим <tex>|R_i|</tex> за <tex>r_i</tex>.
Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex><G, s, t> \in </tex> NCONN.
+
Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in </tex> NCONN.
 +
{{Лемма
 +
| statement = Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
 +
| proof =
 +
Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
 +
    '''Enum'''(<tex>s, i, ri, G</tex>)
 +
    <tex>counter</tex> <tex>\leftarrow</tex> 0                //количество уже найденных и выведенных элементов
 +
    '''for''' <tex>v = 1..n</tex> '''do'''              //перебираем все вершины графа
 +
        '''continue''' or find path      //недетерминированно угадываем путь из s до v или переходим к следующей вершине
 +
        <tex>counter</tex>++
 +
        '''return'''' <tex>v</tex>                //выдаем вершину, до которой угадали путь
 +
    '''if''' (<tex>counter \geq r_i</tex>)            //нашли <tex>r_i</tex> вершин, допускаем, завершаем работу
 +
        '''accept'''
 +
    '''reject'''                  //не нашли <tex>r_i</tex> вершин, не допускаем
 +
   
 +
'''Enum''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.
 +
Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.
 +
Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути.
 +
'''Enum''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий '''accept''', то происходит допуск.
 +
}}
 
}}
 
}}

Версия 13:50, 30 апреля 2012

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


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


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


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

1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому [math]L \in 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]NL \in P.[/math]
[math]\triangleleft[/math]

NL-полнота

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


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

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

Докажем, что CONN[math] \in[/math] NL. Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает [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] памяти.

Теперь докажем, что любая задача из класса NL сводится к задаче CONN с использованием не более чем логарифмической памяти.

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

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

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

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

Определим [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 [/math] NCONN.

Лемма:
Можно построить недетерминированный алгоритм, который будет допускать [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, то происходит допуск.
[math]\triangleleft[/math]
[math]\triangleleft[/math]