Изменения

{{Определение|definition=Задача несуществования пути между двумя заданными вершинами в данном графе <tex>\mathrm{NCONN} = Теорема Иммермана ==\{\langle G, s, t \rangle \bigm|</tex> в графе G нет пути из s в t<tex>\}.</tex>}}

{{ Теорема| statement =<tex>\mathrm{coNL} =\mathrm{NL}.</tex>| proof = Утверждение теоремы ===Очевидно, что язык <tex>\mathrm{NCONN}</tex> является дополнением языка <tex>\mathrm{CONN}</tex>.Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL = coNL}</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>}.Решим задачу STNONCON на логарифмической памятиДругими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.

:Введем обозначение <mathtex>r_i=|R_i|</tex>.Если <tex>t \textnotin R_{STNONCONn-1}</tex>, где <tex>n =\{|V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G=\langle V,E\rangle,s,t\rangle\colon in \textmathrm{ нет пути из NCONN}s\text{ в }t\text{ в графе }G\}.</mathtex>.

Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый Можно построить недетерминированный алгоритм, использующий который будет решать задачу <tex>\mathrm{NCONN}</tex> на <tex>O(\log n|G|)</tex> памяти, которыйпроверяет достижима ли вершина ''t'' из ''s''(это будет доказано ниже).

*В случае недостижимости {{Лемма| statement = Можно построить недетерминированный алгоритм, который будет решать задачу <tex>\mathrm{NCONN}</tex> на <tex>O(\log |G|)</tex> памяти.| proof = Для начала приведем недетерминированный алгоритм, находящий путь между двумя вершинами с длиной не более заданной. '''CheckPath'''(<tex>s,t,k</tex>) <tex>cur \leftarrow s</tex> '''for''' из <tex>i = 1..k</tex> ''s'do''' недетерминированые выборы приводят алгоритм к единице <tex>v \leftarrow_? \left\{1..n\right\}</tex>*Если '''if'''<tex>(cur,v) \notin E</tex> '''reject''' <tex>cur \leftarrow v</tex> '''if''' <tex>cur \ne t</tex> '' достижима из 'reject's'', то вне зависимости от недетерминированых выбором, совершаемых алгоритмом, результат ноль.

Определим Теперь можно построить недетерминированный алгоритм, который будет принимать на вход <tex>r_i</tex> и (в случае корректности <tex>r_i</tex>) будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти. '''REnumerate'''(<subtex>s, i, r_i, G</subtex>) <tex>counter \leftarrow 0 </tex> //количество уже найденных и выведенных элементов ''&nbsp;'for''' <tex>v =&nbsp;{1..n</tex> '''do'v'': существует //перебираем все вершины графа <tex>tryV \leftarrow_? \left\{0, 1\right\}</tex> //недетерминированно угадываем путь из s до v или переходим к следующей вершине '''if'''<tex>tryV = 0</tex> '''continue''' '''CheckPath'''<tex>(s,v,i)</tex> <tex>counter</tex>++ '''output' в ''<tex>v</tex> //выдаем вершину, до которой угадали путь '' длиной ≤ 'if'i''}. Другими словами это множество всех <tex>counter \neq r_i</tex> //не нашли <tex>r_i</tex> вершин,не допускаемдостижимых из '''reject'''s '' не более чем за 'Enumerate'i'' шаговперебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>. Обозначим Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. Теперь, имея '''Enumerate'''R, можно по индукции строить <tex>r_i<sub/tex>. Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>. Пусть известно значение <tex>r_i</tex>. Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i+ 1}</subtex>.   '''Next'| за ''(<tex>s, i, r_i, G</tex>) <tex>r\leftarrow 1</tex> //<tex>r_{i+1}<sub/tex>хотя бы один, так как <tex>s \in R_{i+1}</subtex> '''for'''<tex>v = 1..n</tex> : <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex> '''for''' <tex>u \in V : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex>Заметим '''if''' <tex>u</tex> '''in''' '''Enumerate'''(<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't'' <tex>r</tex>  Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.Для каждого из них перебираются все ребра, в него входящие.Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \notinin R_{i + 1}</tex>.Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''REnumerate'''. Теперь напишем алгоритм, который будет недетерминированно решать задачу <tex>\mathrm{NCONN}</tex> на логарифмической памяти.Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.Вычисление <subtex>r_{n-1}</tex> происходит путем вызова '''Next'''<tex>n- 1</tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.   ''−1'NCONN'''(<tex>G, s, t</tex>) <tex>r_n \leftarrow 1</subtex>, где //<tex>r_0 = 1</tex> '''for'''<tex>i = 0..n- 2</tex> '''do'''&nbsp; //вычисляем <tex>r_{n-1}</tex> <tex>r_n =&nbsp;|</tex> '''Next'V''|(<tex>s, i, r_n, то не существует путь G</tex>) ''s'if' в ''<tex>t</tex> '''in''' '''Enumerate' в графе ''(<tex>s, n - 1, r_n, G</tex>) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> была перечислена, то <tex>t</tex> достижима и выдаем '''reject''', то есть иначе '''accept''' '''reject''' '''else''' '''accept''' Данный алгоритм использует <mathtex>O(\langle log |G|)</tex> памяти,sтак как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>,tи для вызываемых '''Next''' и '''Enumerate''' необходимо <tex>O(\ranglelog |G|)</mathtex> ∈ STNONCONпамяти.}}