Изменения

{{Определение|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 =\{\langle G=\langle |V,E\rangle,s,t\rangle\colon |</tex> нет пути , то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}.</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> памяти. ''R'Enumerate'''(<subtex>s, i, r_i, G</tex>) <tex>counter \leftarrow 0 </subtex> //количество уже найденных и выведенных элементов ''&nbsp;=&nbsp;{'for'v'': существует путь из <tex>v = 1..n</tex> ''s'do' в '' //перебираем все вершины графа <tex>tryV \leftarrow_? \left\{0, 1\right\}</tex> //недетерминированно угадываем путь из s до vили переходим к следующей вершине '' длиной ≤ 'if'i''}. Другими словами это множество всех вершин,<tex>tryV = 0</tex>достижимых из '''continue's'' не более чем за ''i'CheckPath' шагов. Обозначим |''R<subtex>(s,v,i)</subtex>''| за ''r <subtex>icounter</subtex>++ '''output'''.Заметим, что если <tex>t \notin R_{n-1}v</tex> //выдаем вершину, где до которой угадали путь ''n'if'&nbsp;=&nbsp;|''V''|<tex>counter \neq r_i</tex> //не нашли <tex>r_i</tex> вершин, то не существует путь допускаем ''s'reject' в ''t '' в графе 'Enumerate'G'', то есть перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.Для угадывания пути необходимо <mathtex>O(\langle log |G,s,t\rangle|)</mathtex> ∈ STNONCONпамяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути.

Теперь, имея '''ЛеммаEnumerate''': Можно построить алгоритм, который можно по данному ''rиндукции строить <subtex>ir_i</subtex>'' будет перечислять все вершины из ''R. Очевидно, что <subtex>ir_0 = 1</subtex>'' и удачно завершаться на логарифмической памяти. Если ''r, так как <subtex>iR_0</subtex>'' больше истинного размера ''Rсодержит единственную вершину — <subtex>is</subtex>'',. то алгоритм завершится неудачно; однако если ''rПусть известно значение <subtex>ir_i</subtex>'' меньше истинного размера ''R_i''. Напишем программу, то алгоритм завершится удачно, но перечислит лишь некое подмножество ''Rкоторая на логарифмической памяти будет находить <subtex>r_{i+ 1}</subtex>''.

Enum '''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'''(<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> и еще поочередно значения полученные в результате вызова '''Enumerate'''. Теперь напишем алгоритм, который будет недетерминированно решать задачу <tex>\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> '''do''' //вычисляем <tex>r_{n-1}</tex> <tex>r_n = </tex> '''Next'''(<tex>s, i, r_n, G</tex>) '''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> достижима и выдаем ''s'reject''', иначе '''accept''' '''reject''' '''else''' '''accept''' Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>, и для вызываемых '''Next''' и '''Enumerate'''необходимо <tex>O(\log |G|)</tex> памяти.}}