Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
{{Определение
|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>\mathrm{coNL}</tex>''' — множество языков, дополнение до которых принадлежит <tex>\mathrm{NL}</tex>.
}}
==NL-полнота==
{{ Теорема
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|полнаотносительно <tex>\mathrm{\widetilde{L}}</tex>-сведения]].
| proof =
Задача <tex>\mathrm{CONN } = \{\langle G, s, t \rangle\bigm|</tex> : в графе G <tex>\exists </tex> есть путь из s в t<tex>\}</tex>.
Докажем, что <tex>\mathrm{CONN } \in \mathrm{NL}</tex>.Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> — размер входа для задачи , и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
Алгоритм:
1. Начиная с вершины <tex> s </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>L</tex> из <tex>\mathrm{NL}</tex>, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.
| statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex>
| proof =
Решим задачу <tex>\mathrm{NCONN} = \{\langle G, s, t \rangle\bigm|</tex> : в графе G нет пути из s в t<tex>\}</tex>. Очевидно, что этот язык является дополнением языка <tex>\mathrm{CONN}</tex>.
Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL}</tex>, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.
Определим <tex>R_i</tex> = {<tex>v:\bigm|</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>.
