Изменения

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

{{ Теорема| statement === Утверждение теоремы ===<tex>\textmathrm{NLcoNL} = \textmathrm{coNLNL}.</tex>(ffff)=== Доказательство ==| proof =Решим задачу Очевидно, что язык <tex>\textmathrm{STNONCONNCONN}</tex> (''s-t non connectivity'') на логарифмической памяти и покажемявляется дополнением языка <tex>\mathrm{CONN}</tex>.Чтобы показать, что <tex>\textmathrm{STNONCONNCONN} \in \textmathrm{NL}</tex>, придумаем недетерминированный алгоритм, использующий <tex>O(\log |G|)</tex> дополнительной памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.

:Определим <tex>\text{STNONCON}R_i</tex> =\{<tex>v \langle G=\langle V,E\rangle,s,t\rangle\colon bigm|</tex> нет пути существует путь из <tex>s</tex> в <tex>tv</tex> в графе длиной <tex>G\leq i</tex>}.Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex>шагов.

Чтобы показать, что Введем обозначение <tex>\text{STNONCON}r_i=|R_i|</tex> входит в .Если <tex>t \textnotin R_{NLn-1}</tex>, можно придумать недетерминированый алгоритм, использующий где <tex>O(\log n)= |V|</tex> памяти, которыйпроверяет достижима ли вершина то не существует путь из <tex>s</tex> в <tex>t</tex> из в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}</tex>.

*В случае недостижимости Таким образом показано, что <tex>t\mathrm{NCONN} \in \mathrm{NL}</tex> из .Поскольку <tex>\mathrm{CONN} \in \mathrm{NLC}</tex>, то аналогичным образом <tex>s\mathrm{NCONN} \in \mathrm{coNLC}</tex> недетерминированые выборы приводят алгоритм к допуску.*Если Получаем, что любую задачу из <tex>t\mathrm{coNL}</tex> достижима можно свести к задаче из <tex>s\mathrm{NL}</tex>, то вне зависимости от недетерминированых выборова значит <tex>\mathrm{coNL} \subset \mathrm{NL}</tex>.Из соображений симметрии <tex>\mathrm{NL} \subset \mathrm{coNL}</tex>, совершаемых алгоритмом, алгоритм не приходит к допускуа значит <tex>\mathrm{coNL} = \mathrm{NL}</tex>.}}

Определим {{Лемма| statement = Можно построить недетерминированный алгоритм, который будет решать задачу <tex>R_i = \mathrm{v:NCONN}</tex> существует путь из на <tex>s</tex> в <tex>vO(\log |G|)</tex> памяти.| proof = Для начала приведем недетерминированный алгоритм, находящий путь между двумя вершинами с длиной не более заданной. '''CheckPath'''(<tex>\le i\}s,t,k</tex>. Другими словами это множество всех вершин,)достижимых из <tex>cur \leftarrow s</tex> не более чем за '''for''' <tex>i</tex> шагов= 1.. Обозначим <tex>|R_i|</tex> за <tex>r_ik</tex>.'''do'''Заметим, что если <tex>t v \leftarrow_? \left\notin R_{1..n-1\right\}</tex>, где <tex>n = |V| '''if''' </tex>(cur, то не существует путь <tex>sv) \notin E</tex> в '''reject''' <tex>tcur \leftarrow v</tex> в графе <tex>G</tex>,то есть '''if''' <tex><G, s, cur \ne t> \in \text{STNONCON}</tex>. '''reject'''

'''Лемма''': Можно Теперь можно построить недетерминированный алгоритм, который будет принимать верно заданное на вход <tex>r_i</tex> и (AAAAв случае корректности <tex>r_i</tex>) и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\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_? \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''' <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}<code/tex>Enum '''for''' <tex>v = 1..n</codetex> : <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 R_{i + 1}</tex>'' (∈AAAAAAAA). '''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>2\log |G|</tex>, а для вызываемых <tex>\text{Next}</tex> и <tex>\text{Enum}</tex> необходимо <tex>O(\log |G|)</tex> памяти.

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