Изменения

{{Определение|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 на логарифмической памяти и покажемДругими словами это множество всех вершин, что STNONCON ∈ NLдостижимых из <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's''. Для угадывания пути достаточно <tex>Ou \in V : (u, v) \log |in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex> '''if''' <tex>u</tex> '''in''' '''Enumerate'''(<tex>s, i, r_i, G|</tex>)//перечисляем все вершины из <tex>R_i</tex> памяти, так как необходимо помнить лишь текущую вершину пути и пытаться угадывать следующую. Enum является недетерминированой программой и если существует порядок исполнения, чтобы достичь ACCEPT<tex>u</tex> одна из них, то он достигается.<tex>v \in R_{i+1}</tex> <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата '''break''' '''return''' <tex>r</tex>

Данный алгоритм изначально учитывает <codetex>Next(s</tex>, i, r_i, G) r := 1 //''а затем перебирает всех возможных кандидатов <tex>r_{i+1}v</tex> хотя бы один, так как на попадание в <tex>s \in R_{i + 1}</tex>''. '''for''' v = 1 Для каждого из них перебираются все ребра, в него входящие.. n; Затем перечисляются все вершины из <tex>v \neq sR_i</tex> '''do''' //''перебираем все вершины графаи, если начало нашего ребра было перечислено, кроме s -- это кандидаты на попадание в то <tex>v \in R_{i + 1}</tex>''. '''for''' u : Алгоритм использует <tex>O(u,v\log |G|)∈E '''do''' <//''перебираем все ребраtex> памяти, входящие в так необходимо хранить лишь <tex>v'' Enum(s</tex>, i, r_i, G) //''перечисляем все вершины из <tex>R_iu</tex>'' '''if''' u in output '''then''' //''если u одна из них, то <tex>v \in R_{i + 1}r</tex>и еще поочередно значения полученные в результате вызова '' r++ //'Enumerate'увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата'' break write r</code>.

Данный Теперь напишем алгоритм изначально учитывает ''s'', а затем перебирает всех возможных кандидатов на попадание в который будет недетерминированно решать задачу <tex>R_\mathrm{i + 1NCONN}</tex>на логарифмической памяти. Для каждого из них перебираются все ребра, в него входящие. Затем перечисляются все вершины Он будет состоять из двух частей: вычисление <tex>R_ir_{n-1}</tex> и, если начало нашего ребра было перечислено, то перечисление всех вершин из <tex>v \in R_{i + n - 1}</tex>. Алгоритм использует Вычисление <tex>O(\log |G|)r_{n-1}</tex> памяти, так необходимо хранить лишь происходит путем вызова ''v'Next', ''u''<tex>n - 1</tex> раз, ''r'' и еще поочередно значения полученные при этом каждый раз в результате вызова Enumкачестве <tex>r_i</tex> подставляется новое полученное значение.

'''NCONN'''(<codetex>NONCON(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>) Enum '''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''if', иначе '' t in output 'accept''then' '' //'reject'Если t была перечислена то t достижима и выдаем REJECT, иначе ACCEPT'' REJECT '''else''' ACCEPT </code> '''accept'''

Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения ''<tex>r_n'' </tex> и ''<tex>i'' </tex> необходимо <tex>2O(\log |G|)</tex>, а и для вызываемых '''Next ''' и Enum '''Enumerate''' необходимо <tex>O(\log |G|)</tex> памяти. Таким образом показано, что STNONCON ∈ NL.}}