editor
143
правки
Изменения
Нет описания правки
{{Определение
|definition='''Класс <tex>\mathrm{NL}</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.
<tex>\mathrm{NL } = \mathrm{NSPACE}(O(\log n))</tex>
}}
{{Определение
|definition='''Класс <tex>\mathrm{coNL}</tex>''' — множество языков, дополнение до которых принадлежит <tex>NL</tex>.
}}
{{ Теорема
| statement = <tex>L \in \mathrm{NL } \in P.</tex>
| proof =
1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>L \in \mathrm{NL}</tex>.2. Число конфигураций машины, использующей <tex>O(\log n)</tex> памяти не превышает <tex>2^{O(\log n)} = n^{O(1)} = poly(n)</tex>, а, следовательно, машина завершает свою работу за <tex>O(poly(n))</tex> времени. Следовательно, <tex>\mathrm{NL } \in P.</tex>
}}
==NL-полнота==
{{Определение
|definition='''Язык <tex>X</tex>'''называют <tex>\mathrm{NL}</tex>-полным, если <tex>X \in \mathrm{NL}</tex> и <tex>\forall Y : Y \in NL, Y \leq_L X</tex>.
}}
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.
| proof =
Задача <tex>\textmathrm{CONN} = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.
Докажем, что CONN<tex> \mathrm{CONN} \in\mathrm{NL}</tex> NL.
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
Теперь докажем, что любая задача из класса <tex>\mathrm{NL }</tex> сводится к задаче <tex>\mathrm{CONN }</tex> с использованием не более чем логарифмической памяти.
Необходимо по данной задаче из <tex>\mathrm{NL }</tex> построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи <tex>\mathrm{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> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из <tex>\mathrm{L }</tex> в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходы из него и проверка возможности перехода.
| statement = <tex>NL = coNL.</tex>
| proof =
Решим задачу <tex><tex>\textmathrm{NCONN} = \{\langle G, s, t \rangle</tex> : в графе G нет пути из s в t<tex>\}</tex>. Очевидно, что этот язык является дополнением языка <tex>\mathrm{CONN}</tex>.Чтобы показать, что <tex>\mathrm{NCONN }</tex>\in\mathrm{NL}</tex> NL, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет, достижима ли вершина t из s.
Определим <tex>R_i</tex> = {<tex>v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>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>\langle G, s, t \rangle \in \mathrm{NCONN}</tex> NCONN.
{{Лемма
| statement = Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''Enum'''.
Теперь напишем алгоритм, который будет недетерминированно решать задачу '''<tex>\mathrm{NCONN''' }</tex> на логарифмической памяти.
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.
Вычисление <tex>r_{n-1}</tex> происходит путем вызова '''Next''' <tex>n - 1</tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>, и для вызываемых '''Next''' и '''Enum''' необходимо <tex>O(\log |G|)</tex> памяти.
Таким образом показано, что '''NCONN''' <tex>\mathrm{NCONN} \in\mathrm{NL}</tex> '''NL'''.Поскольку '''CONN''' <tex>\mathrm{CONN} \in\mathrm{NLC}</tex> '''NLC''', то аналогичным образом '''NCONN''' <tex>\mathrm{NCONN} \in\mathrm{coNLC}</tex> '''coNLC'''.Получаем, что любую задачу из '''<tex>\mathrm{coNL''' }</tex> можно свести к задаче из '''<tex>\mathrm{NL'''}</tex>, а значит '''<tex>\mathrm{coNL''' ⊂ '''} \subset \mathrm{NL'''}</tex>.Из соображений симметрии ''' <tex>\mathrm{NL''' ⊂ '''} \subset \mathrm{coNL'''}</tex>, а значит ''' <tex>\mathrm{coNL} = \mathrm{NL''' = '''coNL'''}</tex>..
}}
}}
