Теорема Иммермана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Исправлено доказательство)
(не показаны 4 промежуточные версии 3 участников)
Строка 1: Строка 1:
== Теорема Иммермана ==
+
{{Определение
 +
|definition=Задача несуществования пути между двумя заданными вершинами в данном графе <tex>\mathrm{NCONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G нет пути из s в t<tex>\}.</tex>
 +
}}
  
=== Утверждение теоремы ===
+
{{ Теорема
'''NL''' = '''co-NL'''
+
| statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex>
 +
| proof =  
 +
Очевидно, что язык <tex>\mathrm{NCONN}</tex> является дополнением языка <tex>\mathrm{CONN}</tex>.
 +
Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL}</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''' (''s-t non connectivity'') на логарифмической памяти и покажем, что '''STNONCON''' ∈ '''NL'''.
+
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.
  
:<tex>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon </tex> нет пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G\}</tex>
+
Введем обозначение <tex>r_i=|R_i|</tex>.
 +
Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}</tex>.
  
Чтобы показать, что '''STNONCON''' входит в '''NL''', придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который
+
Можно построить недетерминированный алгоритм, который будет решать задачу <tex>\mathrm{NCONN}</tex> на <tex>O(\log |G|)</tex> памяти (это будет доказано ниже).
проверяет достижима ли вершина <tex>t</tex> из <tex>s</tex>.
 
  
Чтобы показать правильность работы алгоритма требуется:
+
Таким образом показано, что <tex>\mathrm{NCONN} \in \mathrm{NL}</tex>.
 +
Поскольку <tex>\mathrm{CONN} \in \mathrm{NLC}</tex>, то аналогичным образом <tex>\mathrm{NCONN} \in \mathrm{coNLC}</tex>.
 +
Получаем, что любую задачу из <tex>\mathrm{coNL}</tex> можно свести к задаче из <tex>\mathrm{NL}</tex>, а значит <tex>\mathrm{coNL} \subset \mathrm{NL}</tex>.
 +
Из соображений симметрии  <tex>\mathrm{NL} \subset \mathrm{coNL}</tex>, а значит  <tex>\mathrm{coNL} = \mathrm{NL}</tex>.
 +
}}
  
*В случае недостижимости <tex>t</tex> из <tex>s</tex> недетерминированные выборы приводят алгоритм к допуску.
+
{{Лемма
*Если <tex>t</tex> достижима из <tex>s</tex>, то вне зависимости от недетерминированных выборов, совершаемых алгоритмом, алгоритм не приходит к допуску.
+
| 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> '''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>v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной ≤ <tex>i</tex>}.
+
Теперь можно построить недетерминированный алгоритм, который будет принимать на вход <tex>r_i</tex> и (в случае корректности <tex>r_i</tex>) будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.
+
  '''Enumerate'''(<tex>s, i, r_i, G</tex>)
Обозначим <tex>|R_i|</tex> за <tex>r_i</tex>.
+
     <tex>counter \leftarrow 0 </tex>                  //количество уже найденных и выведенных элементов
Если <tex>t</tex> ∉ <tex>R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex><G, s, t></tex>&nbsp;∈&nbsp;'''STNONCON'''.
+
     '''for''' <tex>v = 1..n</tex> '''do'''               //перебираем все вершины графа
 
+
       <tex>tryV \leftarrow_? \left\{0, 1\right\}</tex>             //недетерминированно угадываем путь из s до v или переходим к следующей вершине
'''Лемма''': Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
+
      '''if''' <tex>tryV = 0</tex>
 
+
        '''continue'''
<code>
+
       '''CheckPath'''<tex>(s,v,i)</tex>
  Enum(s, i, r<sub>i</sub>, G)
+
      <tex>counter</tex>++
     counter := 0                         //''количество уже найденных и выведенных элементов''
+
       '''output''' <tex>v</tex>                  //выдаем вершину, до которой угадали путь
     '''for''' v = 1..n '''do'''                     //''перебираем все вершины графа''
+
    '''if''' <tex>counter \neq r_i</tex>              //не нашли <tex>r_i</tex> вершин, не допускаем
       '''continue''' or ''find path''             //''недетерминированно угадываем путь из s до v или переходим к следующей вершине''
+
      '''reject'''
       counter++
+
      
       '''yield return''' v                     //''выдаем вершину, до которой угадали путь''
+
'''Enumerate''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.
      '''if''' counter ≥ r<sub>i</sub> '''then'''               //''нашли r<sub>i</sub> вершин, допускаем завершаем работу''
 
        '''ACCEPT'''
 
     '''REJECT'''                              //''не нашли r<sub>i</sub> вершин, не допускаем''
 
</code>
 
 
 
<code>Enum</code> перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.
 
 
Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.
 
Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.
Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути.
+
Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути.
<code>Enum</code> является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий <code>ACCEPT</code>, то происходит допуск.
 
  
Теперь имея <code>Enum</code>, можно индуктивно находить <tex>r_i</tex>.               
+
Теперь, имея '''Enumerate''', можно по индукции строить <tex>r_i</tex>.               
 
Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>.  
 
Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>.  
 
Пусть известно значение <tex>r_i</tex>.  
 
Пусть известно значение <tex>r_i</tex>.  
 
Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i + 1}</tex>.
 
Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i + 1}</tex>.
  
<code>
+
 
   Next(s, i, r<sub>i</sub>, G)
+
   '''Next'''(<tex>s, i, r_i, G</tex>)
     r := 1                               //''r<sub>i+1</sub> хотя бы один, так как s ∈ R<sub>i+1</sub>''
+
     <tex>r \leftarrow 1</tex>                          //<tex>r_{i+1}</tex> хотя бы один, так как <tex>s \in R_{i+1}</tex>
     '''for''' v = 1..n; v s '''do'''               //''перебираем все вершины графа, кроме s — это кандидаты на попадание в R<sub>i+1</sub>''
+
     '''for''' <tex>v = 1..n</tex> : <tex>v \ne s</tex> '''do'''         //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex>
       '''for''' u : (u,v) E '''do'''               //''перебираем все ребра, входящие в v''
+
       '''for''' <tex>u \in V : (u, v) \in E</tex> '''do'''       //перебираем все ребра, входящие в <tex>v</tex>
         '''if''' u '''in''' Enum(s, i, r<sub>i</sub>, G) '''then'''  //''перечисляем все вершины из R<sub>i</sub>, если u одна из них, то v ∈ R<sub>i+1</sub>''
+
         '''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>
           r++                           //''увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата''
+
           <tex>r</tex>++                       //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата
 
           '''break'''  
 
           '''break'''  
     '''return''' r
+
     '''return''' <tex>r</tex>
</code>
+
 
  
 
Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.
 
Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.
 
Для каждого из них перебираются все ребра, в него входящие.
 
Для каждого из них перебираются все ребра, в него входящие.
 
Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in 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> и еще поочередно значения полученные в результате вызова <code>Enum</code>.
+
Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''Enumerate'''.
  
Теперь напишем алгоритм, который будет недетерминированно решать задачу '''STNONCON''' на логарифмической памяти.
+
Теперь напишем алгоритм, который будет недетерминированно решать задачу <tex>\mathrm{NCONN}</tex> на логарифмической памяти.
 
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.
 
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.
Вычисление <tex>r_{n-1}</tex> происходит путем вызова <code>Next</code> (n - 1) раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.
+
Вычисление <tex>r_{n-1}</tex> происходит путем вызова '''Next''' <tex>n - 1</tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.
 +
 
  
<code>
+
  '''NCONN'''(<tex>G, s, t</tex>)
  NONCON(G, s, t)
+
     <tex>r_n \leftarrow 1</tex>                           //<tex>r_0 = 1</tex>
     r<sub>n</sub> := 1                              //''r<sub>0</sub> = 1''
+
     '''for''' <tex>i = 0..n - 2</tex> '''do'''                 //вычисляем <tex>r_{n-1}</tex>
     '''for''' i = 0..(n - 2) '''do'''               //''вычисляем r<sub>n-1</sub>''
+
       <tex>r_n = </tex> '''Next'''(<tex>s, i, r_n, G</tex>)
       r<sub>n</sub> := Next(s, i, r<sub>n</sub>, G)
+
     '''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'''
     '''if''' t in Enum(s, n - 1, r<sub>n</sub>, G) '''then'''   //''перечисляем вершины из R<sub>n-1</sub>, если t была перечислена, то t достижима и выдаем REJECT, иначе ACCEPT''
+
       '''reject'''
       '''REJECT'''
 
 
     '''else'''
 
     '''else'''
       '''ACCEPT'''
+
       '''accept'''
</code>
 
 
 
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>,
 
и для вызываемых <code>Next</code> и <code>Enum</code> необходимо <tex>O(\log |G|)</tex> памяти.
 
  
Таким образом показано, что '''STNONCON''' ∈ '''NL'''.
+
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>, и для вызываемых '''Next''' и '''Enumerate''' необходимо <tex>O(\log |G|)</tex> памяти.
Поскольку '''STNONCON''' ∈ '''co-NLC''', то получаем, что любую задачу из '''co-NL''' можно свести к задаче из '''NL''', а значит '''co-NL''' '''NL'''.
+
}}
Из соображений симметрии '''NL''' ⊂ '''co-NL''', а значит '''NL''' = '''co-NL'''.
 

Версия 19:50, 14 марта 2013

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


Теорема:
[math]\mathrm{coNL} = \mathrm{NL}.[/math]
Доказательство:
[math]\triangleright[/math]

Очевидно, что язык [math]\mathrm{NCONN}[/math] является дополнением языка [math]\mathrm{CONN}[/math]. Чтобы показать, что [math]\mathrm{NCONN}\in \mathrm{NL}[/math], придумаем недетерминированный алгоритм, использующий [math]O(\log |G|)[/math] дополнительной памяти, который проверяет, достижима ли вершина [math]t[/math] из [math]s[/math].

Определим [math]R_i[/math] = {[math]v \bigm|[/math] существует путь из [math]s[/math] в [math]v[/math] длиной [math]\leq i[/math]}. Другими словами это множество всех вершин, достижимых из [math]s[/math] не более чем за [math]i[/math] шагов.

Введем обозначение [math]r_i=|R_i|[/math]. Если [math]t \notin R_{n-1}[/math], где [math]n = |V|[/math], то не существует путь из [math]s[/math] в [math]t[/math] в графе [math]G[/math], то есть [math]\langle G, s, t \rangle \in \mathrm{NCONN}[/math].

Можно построить недетерминированный алгоритм, который будет решать задачу [math]\mathrm{NCONN}[/math] на [math]O(\log |G|)[/math] памяти (это будет доказано ниже).

Таким образом показано, что [math]\mathrm{NCONN} \in \mathrm{NL}[/math]. Поскольку [math]\mathrm{CONN} \in \mathrm{NLC}[/math], то аналогичным образом [math]\mathrm{NCONN} \in \mathrm{coNLC}[/math]. Получаем, что любую задачу из [math]\mathrm{coNL}[/math] можно свести к задаче из [math]\mathrm{NL}[/math], а значит [math]\mathrm{coNL} \subset \mathrm{NL}[/math].

Из соображений симметрии [math]\mathrm{NL} \subset \mathrm{coNL}[/math], а значит [math]\mathrm{coNL} = \mathrm{NL}[/math].
[math]\triangleleft[/math]
Лемма:
Можно построить недетерминированный алгоритм, который будет решать задачу [math]\mathrm{NCONN}[/math] на [math]O(\log |G|)[/math] памяти.
Доказательство:
[math]\triangleright[/math]

Для начала приведем недетерминированный алгоритм, находящий путь между двумя вершинами с длиной не более заданной.

 CheckPath([math]s,t,k[/math])
   [math]cur \leftarrow s[/math]
   for [math]i = 1..k[/math] do
     [math]v \leftarrow_? \left\{1..n\right\}[/math]
     if [math](cur,v) \notin E[/math]
       reject
     [math]cur \leftarrow v[/math]
   if [math]cur \ne t[/math]
     reject

Теперь можно построить недетерминированный алгоритм, который будет принимать на вход [math]r_i[/math] и (в случае корректности [math]r_i[/math]) будет перечислять все вершины из [math]R_i[/math] на [math]O(\log |G|)[/math] памяти.

 Enumerate([math]s, i, r_i, G[/math])
   [math]counter \leftarrow 0 [/math]                  //количество уже найденных и выведенных элементов
   for [math]v = 1..n[/math] do               //перебираем все вершины графа
     [math]tryV \leftarrow_? \left\{0, 1\right\}[/math]              //недетерминированно угадываем путь из s до v или переходим к следующей вершине
     if [math]tryV = 0[/math]
       continue
     CheckPath[math](s,v,i)[/math]
     [math]counter[/math]++
     output [math]v[/math]                   //выдаем вершину, до которой угадали путь
   if [math]counter \neq r_i[/math]               //не нашли [math]r_i[/math] вершин, не допускаем
     reject
   

Enumerate перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из [math]s[/math]. Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из [math]s[/math] в [math]v[/math]. Для угадывания пути необходимо [math]O(\log |G|)[/math] памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути.

Теперь, имея Enumerate, можно по индукции строить [math]r_i[/math]. Очевидно, что [math]r_0 = 1[/math], так как [math]R_0[/math] содержит единственную вершину — [math]s[/math]. Пусть известно значение [math]r_i[/math]. Напишем программу, которая на логарифмической памяти будет находить [math]r_{i + 1}[/math].


 Next([math]s, i, r_i, G[/math])
   [math]r \leftarrow 1[/math]                           //[math]r_{i+1}[/math] хотя бы один, так как [math]s \in R_{i+1}[/math]
   for [math]v = 1..n[/math] : [math]v \ne s[/math] do          //перебираем все вершины графа, кроме [math]s[/math] — это кандидаты на попадание в [math]R_{i+1}[/math]
     for [math]u \in V : (u, v) \in E[/math] do       //перебираем все ребра, входящие в [math]v[/math]
       if [math]u[/math] in Enumerate([math]s, i, r_i, G[/math]) //перечисляем все вершины из [math]R_i[/math], если [math]u[/math] одна из них, то [math]v \in R_{i+1}[/math]
         [math]r[/math]++                       //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата
         break 
   return [math]r[/math]


Данный алгоритм изначально учитывает [math]s[/math], а затем перебирает всех возможных кандидатов [math]v[/math] на попадание в [math]R_{i + 1}[/math]. Для каждого из них перебираются все ребра, в него входящие. Затем перечисляются все вершины из [math]R_i[/math] и, если начало нашего ребра было перечислено, то [math]v \in R_{i + 1}[/math]. Алгоритм использует [math]O(\log |G|)[/math] памяти, так необходимо хранить лишь [math]v[/math], [math]u[/math], [math]r[/math] и еще поочередно значения полученные в результате вызова Enumerate.

Теперь напишем алгоритм, который будет недетерминированно решать задачу [math]\mathrm{NCONN}[/math] на логарифмической памяти. Он будет состоять из двух частей: вычисление [math]r_{n-1}[/math] и перечисление всех вершин из [math]R_{n - 1}[/math]. Вычисление [math]r_{n-1}[/math] происходит путем вызова Next [math]n - 1[/math] раз, при этом каждый раз в качестве [math]r_i[/math] подставляется новое полученное значение.


 NCONN([math]G, s, t[/math])
   [math]r_n \leftarrow 1[/math]                            //[math]r_0 = 1[/math]
   for [math]i = 0..n - 2[/math] do                 //вычисляем [math]r_{n-1}[/math]
     [math]r_n = [/math] Next([math]s, i, r_n, G[/math])
   if [math]t[/math] in Enumerate([math]s, n - 1, r_n, G[/math])   //перечисляем вершины из [math]R_{n-1}[/math], если [math]t[/math] была перечислена, то [math]t[/math] достижима и выдаем reject, иначе accept
     reject
   else
     accept
Данный алгоритм использует [math]O(\log |G|)[/math] памяти, так как для хранения [math]r_n[/math] и [math]i[/math] необходимо [math]O(\log |G|)[/math], и для вызываемых Next и Enumerate необходимо [math]O(\log |G|)[/math] памяти.
[math]\triangleleft[/math]