Изменения

{{Определение|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> шагов.

:Введем обозначение <tex>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 \mbox{ нет пути из }s\mbox{ в }tin \mboxmathrm{ в графе NCONN}G\}.</tex>.

Чтобы показать, что 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> памяти. '''Enumerate'''R(<subtex>s, i, r_i, G</subtex>) <tex>counter \leftarrow 0 </tex> //количество уже найденных и выведенных элементов '''for'''&nbsp;<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''' '''Enumerate''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.достижимых Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. Теперь, имея '''Enumerate''', можно по индукции строить <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 \leftarrow 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>s \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 \in V : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex> '''if''' <tex>u</tex> '''in''' '''Enumerate'''R(<tex>s, i, r_i, G</tex>) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <subtex>v \in R_{i+1}</subtex> <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата '''| за break''' '''return'''<tex>r<sub/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</subtex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''Enumerate'''.ЗаметимТеперь напишем алгоритм, что если который будет недетерминированно решать задачу <tex>t \notin mathrm{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 \leftarrow 1</tex> //<tex>r_0 = 1</tex> '''for''' <tex>i = 0..n- 2</tex> '''&nbsp;do''' //вычисляем <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памяти.}}