Классы L, NL, coNL. NL-полнота задачи о достижимости — различия между версиями
(→Теорема Иммермана) |
(→Теорема Иммермана) |
||
Строка 86: | Строка 86: | ||
Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. | Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. | ||
'''Enum''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий '''accept''', то происходит допуск. | '''Enum''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий '''accept''', то происходит допуск. | ||
+ | |||
+ | Теперь, имея '''Enum''', можно по индукции находить <tex>r_i</tex>. | ||
+ | Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>. | ||
+ | Пусть известно значение <tex>r_i</tex>. | ||
+ | Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i + 1}</tex>. | ||
+ | |||
+ | |||
+ | '''Next'''(<tex>s, i, r_i, G</tex>) | ||
+ | <tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r \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>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</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>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>. | ||
+ | Вычисление <tex>r_{n-1}</tex> происходит путем вызова <code>Next</code> (n - 1) раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение. | ||
+ | |||
+ | <code> | ||
+ | NONCON(G, s, t) | ||
+ | r<sub>n</sub> := 1 //''r<sub>0</sub> = 1'' | ||
+ | '''for''' i = 0..(n - 2) '''do''' //''вычисляем r<sub>n-1</sub>'' | ||
+ | r<sub>n</sub> := Next(s, i, r<sub>n</sub>, G) | ||
+ | '''if''' t '''in''' Enum(s, n - 1, r<sub>n</sub>, G) '''then''' //''перечисляем вершины из R<sub>n-1</sub>, если t была перечислена, то t достижима и выдаем REJECT, иначе ACCEPT'' | ||
+ | '''REJECT''' | ||
+ | '''else''' | ||
+ | '''ACCEPT''' | ||
+ | </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> памяти. | ||
+ | |||
+ | Таким образом показано, что '''STNONCON''' ∈ '''NL'''. | ||
+ | Поскольку '''[[NL-полнота задачи о достижимости в графе|STCON]]''' ∈ '''[[NL-полнота|NLC]]''', то аналогичным образом '''STNONCON''' ∈ '''co-NLC'''. | ||
+ | Получаем, что любую задачу из '''co-NL''' можно свести к задаче из '''NL''', а значит '''co-NL''' ⊂ '''NL'''. | ||
+ | Из соображений симметрии '''NL''' ⊂ '''co-NL''', а значит '''NL''' = '''co-NL'''. | ||
+ | |||
}} | }} | ||
}} | }} |
Версия 17:25, 13 мая 2012
Определение: |
Класс | — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной .
Определение: |
Класс | — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной .
Определение: |
Класс | — множество языков, дополнение до которых принадлежит .
Теорема: |
Доказательство: |
1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому 2. Число конфигураций машины, использующей . памяти не превышает , а, следовательно, машина завершает свою работу за времени. Следовательно, |
NL-полнота
Определение: |
Язык | называют -полным, если и .
Теорема: |
Задача существования пути между двумя заданными вершинами в данном графе NL-полна. |
Доказательство: |
Задача : в графе G путь из s в t .Докажем, что CONN NL. Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает памяти, где - размер входа для задачи и за время порядка решает эту задачу.Алгоритм 1. Начиная с вершины недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)2. Проверяем, правда ли, что текущая вершина совпадает с . Если это так, возвращает TRUE.3. Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды. Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают памяти.Теперь докажем, что любая задача из класса NL сводится к задаче CONN с использованием не более чем логарифмической памяти. Необходимо по данной задаче из NL построить тройку , решение задачи CONN для которой будет эквивалентно решению данной задачи.Любая машина Тьюринга, которая принимает некоторый язык L из NL, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга . Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в , а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) — ребро в графе . За вершину принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину .Очевидно, что для любого слова из языка L, то есть принимаемого данной машиной Тьюринга, будет существовать путь из Такое построение графа в в построенном графе . А если для некоторого слова не из L в существует путь из в , то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной. по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их , потому переменная, перебирающая его занимает памяти), переходы из него и проверка возможности перехода. |
Теорема Иммермана
Теорема: | ||||||
Доказательство: | ||||||
Решим задачу : в графе G нет пути из s в t . Очевидно, что этот язык является дополнением языка CONN. Чтобы показать, что NCONN NL, придумаем недетерминированый алгоритм, использующий памяти, который проверяет, достижима ли вершина t из s.Определим = { существует путь из в длиной }. Другими словами это множество всех вершин, достижимых из не более чем за шагов. Обозначим за . Если , где , то не существует путь из в в графе , то есть NCONN.
| ||||||