editor
143
правки
Изменения
Новая страница: «{{Определение |definition='''Класс <tex>L</tex>''' — множество языков, разрешимых на детерминированно...»
{{Определение
|definition='''Класс <tex>L</tex>''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.
<tex>L = DSPACE(O(\log n))</tex>
}}
{{Определение
|definition='''Класс <tex>NL</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.
<tex>NL = NSPACE(O(\log n))</tex>
}}
{{Определение
|definition='''Класс <tex>coNL</tex>''' — множество языков, дополнение до которых принадлежит <tex>NL</tex>.
}}
{{ Теорема
| statement = <tex>L \in NL \in P.</tex>
| proof =
1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>L \in 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>NL \in P.</tex>
}}
==NL-полнота==
{{Определение
|definition='''Язык <tex>X</tex>'''называют <tex>NL</tex>-полным, если <tex>X \in NL</tex> и <tex>\forall Y : Y \in NL, Y \leq_L X</tex>.
}}
{{ Теорема
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.
| proof =
Задача <tex>\text{CONN} = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.
Докажем, что CONN<tex> \in</tex> NL.
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
Алгоритм
1. Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)
2. Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает TRUE.
3. Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
Теперь докажем, что любая задача из класса NL сводится к задаче CONN с использованием не более чем логарифмической памяти.
Необходимо по данной задаче из NL построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи CONN для которой будет эквивалентно решению данной задачи.
Любая машина Тьюринга, которая принимает некоторый язык L из NL, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.
Очевидно, что для любого слова из языка L, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из L в <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>\text{NCONN} = \{\langle G, s, t \rangle</tex> : в графе G нет пути из s в t<tex>\}</tex>. Очевидно, что этот язык является дополнением языка CONN.
Чтобы показать, что NCONN <tex>\in</tex> NL, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет достижима ли вершина t из s.
}}
|definition='''Класс <tex>L</tex>''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.
<tex>L = DSPACE(O(\log n))</tex>
}}
{{Определение
|definition='''Класс <tex>NL</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.
<tex>NL = NSPACE(O(\log n))</tex>
}}
{{Определение
|definition='''Класс <tex>coNL</tex>''' — множество языков, дополнение до которых принадлежит <tex>NL</tex>.
}}
{{ Теорема
| statement = <tex>L \in NL \in P.</tex>
| proof =
1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>L \in 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>NL \in P.</tex>
}}
==NL-полнота==
{{Определение
|definition='''Язык <tex>X</tex>'''называют <tex>NL</tex>-полным, если <tex>X \in NL</tex> и <tex>\forall Y : Y \in NL, Y \leq_L X</tex>.
}}
{{ Теорема
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.
| proof =
Задача <tex>\text{CONN} = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.
Докажем, что CONN<tex> \in</tex> NL.
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
Алгоритм
1. Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)
2. Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает TRUE.
3. Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
Теперь докажем, что любая задача из класса NL сводится к задаче CONN с использованием не более чем логарифмической памяти.
Необходимо по данной задаче из NL построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи CONN для которой будет эквивалентно решению данной задачи.
Любая машина Тьюринга, которая принимает некоторый язык L из NL, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.
Очевидно, что для любого слова из языка L, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из L в <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>\text{NCONN} = \{\langle G, s, t \rangle</tex> : в графе G нет пути из s в t<tex>\}</tex>. Очевидно, что этот язык является дополнением языка CONN.
Чтобы показать, что NCONN <tex>\in</tex> NL, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет достижима ли вершина t из s.
}}
