202
правки
Изменения
Нет описания правки
{{Определение
|definition='''Класс <tex>\mathrm{L}</tex>''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<tex>\mathrm{L } = \mathrm{DSPACE(O}(\log n))</tex>.
}}
{{Определение
|definition='''Класс <tex>\mathrm{NL}</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<tex>\mathrm{NL } = \mathrm{NSPACE(O}(\log n))</tex>}} {{Определение|definition='''Класс <tex>coNL</tex>''' — множество языков, дополнение до которых принадлежит <tex>NL</tex>.
}}
{{ Теорема
| statement = <tex>\mathrm{L } \in subset \mathrm{NL } \subset \in mathrm{P}.</tex>
| proof =
}}
==NL-полнота==
{{Определение|definition='''Язык Задача <tex>X</tex>'''называют <tex>NL</tex>-полным\mathrm{CONN} = \{\langle G, s, если <tex>X t \rangle \in NLbigm|</tex> и в графе G есть путь из s в t<tex>\forall Y : Y \in NL, Y \leq_L X}</tex>{{---}} задача существования пути между двумя заданными вершинами в данном графе.
}}
{{ Теорема
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|полнаотносительно <tex>\mathrm{\widetilde{L}}</tex>-сведения]].
| proof =
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <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>L </tex> из <tex>\mathrm{NL}</tex>, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </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> памяти), переходы переходов из него и проверка проверки возможности перехода.
}}
==Теорема Иммермана==
{{Определение
|definition=Задача несуществования пути между двумя заданными вершинами в данном графе <tex>\mathrm{NCONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G нет пути из s в t<tex>\}.</tex>
}}
{{ Теорема
| statement = <tex>\mathrm{coNL} = \mathrm{NL = coNL}.</tex>
| proof =
Определим <tex>R_i</tex> = {<tex>v:\bigm|</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.
{{Лемма
| 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> памяти.
<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> вершин, допускаем, завершаем работу
'''Enum''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.
'''Next'''(<tex>s, i, r_i, G</tex>)
<tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r s \in R_{i+1}</tex> '''for''' <tex>v = 1..n</tex>; <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex> '''for''' <tex>u : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex> '''if''' (<tex>u</tex> '''in''' '''Enum'''(<tex>s, i, r_i, G</tex>)) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</tex> <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата
'''break'''
'''return''' <tex>r</tex>
Для каждого из них перебираются все ребра, в него входящие.
Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</tex>.
Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова <code>'''Enum</code>'''.
Теперь напишем алгоритм, который будет недетерминированно решать задачу '''STNONCON''' <tex>\mathrm{NCONN}</tex> на логарифмической памяти.
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.
Вычисление <tex>r_{n-1}</tex> происходит путем вызова <code>'''Next''' </codetex> (n - 1) </tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.
'''NCONN'''(<codetex> NONCON(G, s, t</tex>) r<subtex>nr_n = 1</subtex> := 1 //''r<subtex>0r_0 = 1</subtex> = 1'' '''for''' <tex>i = 0..(n - 2) </tex> '''do''' //''вычисляем r<subtex>r_{n-1}</subtex>'' r<subtex>nr_n = </subtex> := '''Next'''(<tex>s, i, r<sub>nr_n, G</subtex>, G) '''if''' t (<tex>t1</tex> '''in''' ''' Enum'''(<tex>s, n - 1, r<sub>nr_n, G</subtex>, G) '''then''' ) //''перечисляем вершины из R<subtex>R_{n-1}</subtex>, если <tex>t </tex> была перечислена, то <tex>t </tex> достижима и выдаем REJECT'''reject''', иначе ACCEPT'''accept''' '''REJECTreject'''
'''else'''
'''ACCEPTaccept'''</code>
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>,и для вызываемых <code>'''Next</code> ''' и <code>'''Enum</code> ''' необходимо <tex>O(\log |G|)</tex> памяти.}}