Изменения

|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>

1. #Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>\mathrm{L } \in subset \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 } \subset \in mathrm{P}.</tex>

{{Определение|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>-сведения]].

Задача Докажем, что <tex>\textmathrm{CONN} = \in \mathrm{\langle GNL}</tex>.Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, sкоторый использует конечное число переменных, t каждая из которых занимает <tex> O(\ranglelog n) </tex> : в графе G памяти, где <tex>\exists n </tex> путь из s в t— размер входа, и за время порядка <tex>\}O(poly(n)) </tex>решает эту задачу.

Докажем, что CONNАлгоритм: #Начиная с вершины <tex> \ins </tex> NLнедетерминированно переходим в одну из вершин, смежных с ней.Для доказательства (Очевидно, для этого необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных).#Проверяем, каждая из которых занимает правда ли, что текущая вершина совпадает с <tex> O(\log n) t </tex> памяти. Если это так, возвращает TRUE.#Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды. Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, где финальную вершину <tex> n t </tex> - размер входа и некоторое число вспомогательных переменных, для задачи и за время порядка совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(poly(\log n)) </tex> решает эту задачупамяти.

1. Начиная с вершины Необходимо по данной задаче из <tex>\mathrm{NL}</tex> построить тройку <tex> \langle G, s , t \rangle </tex> недетерминированно переходим в одну из вершин, смежных с нейрешение задачи <tex>\mathrm{CONN}</tex> для которой будет эквивалентно решению данной задачи. (Очевидно, для этого необходимо конечное число переменных)

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

3Очевидно, что для любого слова из языка <tex>L</tex>, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин А если для некоторого слова не из <tex>L</tex> в <tex> G </tex> существует путь из <tex> s </tex> в графе<tex> t </tex>, возвращаем FALSEто он соответствует некоторой корректной последовательности переходов в изначальной машине, так как посетили некоторую вершину дваждытаким образом слово должно было приниматься этой недетерминированной машиной.

Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину Такое построение графа <tex> t G </tex> и некоторое число вспомогательных по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, для совершения переходов. Все эти переменные принимают значения не болеекоторые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, чем максимальный номер вершиныпотому переменная, то есть как раз занимают перебирающая его занимает <tex> O(\log n) </tex> памяти), переходов из него и проверки возможности перехода.

Любая машина Тьюринга, которая принимает некоторый язык L из NL, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро Определение|definition=Задача несуществования пути между двумя заданными вершинами в данном графе <tex> \mathrm{NCONN} = \{\langle G </tex>. За вершину <tex> , s , t \rangle \bigm|</tex> принимается вершина, соответствующая начальному состоянию машины, а в графе G нет пути из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход s в выделенную вершину t<tex> t \}.</tex>.}}

{{ Теорема| statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex>| proof = Очевидно, что для любого слова из языка L, то есть принимаемого данной машиной Тьюринга, будет существовать путь из язык <tex> s \mathrm{NCONN}</tex> в является дополнением языка <tex> t \mathrm{CONN}</tex> в построенном графе .Чтобы показать, что <tex> G \mathrm{NCONN}\in \mathrm{NL}</tex>. А если для некоторого слова не из L в , придумаем недетерминированый алгоритм, использующий <tex> O(\log |G |)</tex> существует путь из памяти, который проверяет, достижима ли вершина <tex> s t</tex> в из <tex> t s</tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.

Такое построение графа Определим <tex> G R_i</tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их = {<tex>v \bigm|</tex> существует путь из <tex>s</tex> в <tex> O(poly(n)) v</tex>, потому переменная, перебирающая его занимает длиной <tex> O(\log n) leq i</tex> памяти)}.Другими словами это множество всех вершин, переходы достижимых из него и проверка возможности перехода<tex>s</tex> не более чем за <tex>i</tex> шагов.

'''Next'''(<tex>s, i, r_i, G</tex>) <tex>r ==Теорема Иммермана==1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>s \in R_{ Теоремаi+1}</tex>| statement = '''for''' <tex>NL v = coNL1..n</tex>; <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex>| proof = '''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 \textin R_{NCONNi+1}</tex> <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата '''break''' '''return''' <tex>r</tex>  Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1} = </tex>.Для каждого из них перебираются все ребра, в него входящие.Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</tex>.Алгоритм использует <tex>O(\langle log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, s<tex>r</tex> и еще поочередно значения полученные в результате вызова '''Enum'''. Теперь напишем алгоритм, t который будет недетерминированно решать задачу <tex>\ranglemathrm{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> подставляется новое полученное значение.   '''NCONN'''(<tex>G нет пути из , s в , t</tex>) <tex>\}r_n = 1</tex> //<tex>r_0 = 1</tex> '''for''' <tex>i = 0. Очевидно, что этот язык является дополнением языка CONN.n - 2</tex> '''do''' //вычисляем <tex>r_{n-1}</tex>Чтобы показать <tex>r_n = </tex> '''Next'''(<tex>s, i, r_n, что NCONN G</tex>) '''if''' (<tex>t1</tex>\'''in''' '''Enum'''(<tex>s, n - 1, r_n, G</tex>)) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> NLбыла перечислена, придумаем недетерминированый то <tex>t</tex> достижима и выдаем '''reject''', иначе '''accept''' '''reject''' '''else''' '''accept''' Данный алгоритмиспользует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>, использующий и для вызываемых '''Next''' и '''Enum''' необходимо <tex>O(\log |G|)</tex> памяти, который проверяет достижима ли вершина t из s.