Изменения

{{Определение|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>\textmathrm{NLNCONN} = \textin \mathrm{coNLNL}</tex>, придумаем недетерминированный алгоритм, использующий <tex>O(\log |G|)</tex> дополнительной памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.

Определим <tex>R_i</tex> === Доказательство ===Решим задачу {<tex>v \text{STNONCON}bigm|</tex> (''существует путь из <tex>s-t non connectivity'') на логарифмической памяти и покажем, что </tex> в <tex>v</tex> длиной <tex>\text{STNONCON} \in \text{NLleq i</tex>}.Другими словами это множество всех вершин, достижимых из <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>.

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

*В случае недостижимости {{Лемма| statement = Можно построить недетерминированный алгоритм, который будет решать задачу <tex>t\mathrm{NCONN}</tex> из на <tex>sO(\log |G|)</tex> недетерминированые выборы приводят памяти.| proof = Для начала приведем недетерминированный алгоритм к допуску, находящий путь между двумя вершинами с длиной не более заданной.*Если '''CheckPath'''(<tex>s,t,k</tex> достижима из ) <tex>cur \leftarrow s</tex> '''for''' <tex>i = 1..k</tex> '''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'''

Определим Теперь можно построить недетерминированный алгоритм, который будет принимать на вход <tex>r_i</tex> и (в случае корректности <tex>r_i</tex>) будет перечислять все вершины из <tex>R_i = </tex> на <tex>O(\{v:log |G|)</tex> существует путь из памяти. '''Enumerate'''(<tex>s, i, r_i, G</tex>) <tex>counter \leftarrow 0 </tex> в //количество уже найденных и выведенных элементов '''for''' <tex>v= 1..n</tex> длиной '''do''' //перебираем все вершины графа <tex>tryV \leftarrow_? \le ileft\{0, 1\right\}</tex>. Другими словами это множество всех вершин, //недетерминированно угадываем путь из s до v или переходим к следующей вершинедостижимых из '''if''' <tex>stryV = 0</tex> не более чем за '''continue''' '''CheckPath'''<tex>(s,v,i)</tex> шагов. Обозначим <tex>|R_i|counter</tex> за ++ '''output''' <tex>r_iv</tex>. //выдаем вершину, до которой угадали путьЗаметим, что если '''if''' <tex>t counter \notin R_{n-1}neq r_i</tex>, где //не нашли <tex>n = |V|r_i</tex>вершин, то не существует допускаем '''reject''' '''Enumerate''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex> в .Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>ts</tex> в графе <tex>Gv</tex>,.то есть Для угадывания пути необходимо <tex><O(\log |G, s, t> \in \text{STNONCON}|)</tex>памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути.

Теперь, имея '''ЛеммаEnumerate''': Можно построить недетерминированный алгоритм, который будет принимать верно заданное можно по индукции строить <tex>r_i</tex> и при этом будет перечислять все вершины из . Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>. Пусть известно значение <tex>R_ir_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 \textin R_{Enumi+1}</tex> перебирает '''for''' <tex>v = 1..n</tex> : <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на логарифмической памяти и пытается угадать путь до этой вершины из попадание в <tex>sR_{i+1}</tex>.Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути. Для работы необходимо '''for''' <tex>Ou \in V : (u, v) \log |G|)in E</tex> памяти'''do''' //перебираем все ребра, так как необходимо лишь хранить текущуювходящие в <tex>v</tex>и следующую угадываемую '''if''' <tex>u</tex> '''in''' '''Enumerate'''(<tex>s, i, r_i, G</tex>) //перечисляем все вершины угадываемого пути. из <tex>\text{Enum}R_i</tex> является недетерминированым алгоритмом и , если существует порядок исполнения<tex>u</tex> одна из них, чтобы достичь то <tex>v \textin R_{ACCEPTi+1}</tex>, то он достигается. <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата '''break''' '''return''' <tex>r</tex>

Данный алгоритм изначально учитывает <codetex> Next(s, i, <tex>r_i</tex>, 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 : (u,v)Алгоритм использует <tex>O(\inlog |G|)</tex>E '''do''' //''перебираем все ребрапамяти, входящие в v'' //''перечисляем все вершины из так необходимо хранить лишь <tex>R_iv</tex>'' '''if''' u in Enum(s, i, <tex>r_iu</tex>, G) '''then''' //''если u одна из них, то <tex>v \in R_{i + 1}r</tex>'' r++ //''увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата'еще поочередно значения полученные в результате вызова ' ''Enumerate'break''' '''return''' r</code>.

Данный Теперь напишем алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов на попадание в который будет недетерминированно решать задачу <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> памяти, так необходимо хранить лишь происходит путем вызова '''Next''' <tex>vn - 1</tex>раз, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные при этом каждый раз в результате вызова качестве <tex>\text{Enum}r_i</tex>подставляется новое полученное значение.

'''NCONN'''(<codetex> NONCON(G, s, t</tex>) <tex>r_n\leftarrow 1</tex> := 1 //''<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, <tex>r_n, G</tex>, G) //''Перечисляем вершины из 'if''' <tex>R_{n - 1}t</tex>'' 'in''' '''ifEnumerate''' t in Enum(<tex>s, n - 1, r_n, G</tex>) //перечисляем вершины из <tex>r_nR_{n-1}</tex>, G) '''then''' если <tex>t<//''Если t tex> была перечислена , то <tex>t </tex> достижима и выдаем REJECT'''reject''', иначе ACCEPT'''accept''' '''REJECTreject'''

'''ACCEPTaccept'''</code>

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