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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 22: Строка 22:
 
то есть <tex><G, s, t> \in \text{STNONCON}</tex>.
 
то есть <tex><G, s, t> \in \text{STNONCON}</tex>.
  
'''Лемма''': Можно построить алгоритм, который по данному <tex>r_i</tex> будет перечислять все вершины из <tex>R_i</tex> и удачно завершаться на логарифмической памяти. Если <tex>r_i</tex> больше истинного размера <tex>R_i</tex>,
+
'''Лемма''': Можно построить недетерминированный алгоритм, который будет принимать верно заданное <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на логарифмической памяти.
то алгоритм завершится неудачно;
 
однако если <tex>r_i</tex> меньше истинного размера <tex>R_i</tex>, то алгоритм завершится удачно, но перечислит лишь некое подмножество <tex>R_i</tex>.  
 
  
 
<code>
 
<code>
Строка 33: Строка 31:
 
       counter++  
 
       counter++  
 
       yield return v //''выдаем вершину, до которой угадали путь''
 
       yield return v //''выдаем вершину, до которой угадали путь''
       ''if'' counter ≥ r_i ''then'' //''нашли r_i вершин, удачно завершаем работу''
+
       ''if'' counter ≥ r_i ''then'' //''нашли r_i вершин, принимаем и завершаем работу''
 
         ACCEPT
 
         ACCEPT
     REJECT //''не нашли r_i вершин''
+
     REJECT //''не нашли r_i вершин, отклоняем''
 
</code>
 
</code>
  
<tex>Enum</tex> перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>. Для угадывания пути достаточно <tex>O(\log |G|)</tex> памяти, так как необходимо помнить лишь текущую вершину пути и пытаться угадывать следующую. <tex>Enum</tex> является недетерминированой программой и если существует порядок исполнения, чтобы достичь ACCEPT, то он достигается.
+
<tex>Enum</tex> перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.
 +
Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути. Для работы необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую
 +
и следующую угадываемую вершины угадываемого пути.  
 +
<tex>Enum</tex> является недетерминированым алгоритмом и если существует порядок исполнения, чтобы достичь ACCEPT, то он достигается.
  
 
Теперь имея <tex>Enum</tex>, можно индуктивно находить <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>.
 
Теперь имея <tex>Enum</tex>, можно индуктивно находить <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>.
Строка 72: Строка 73:
 
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>2\log |G|</tex>, а для вызываемых Next и Enum необходимо <tex>O(\log |G|)</tex> памяти.
 
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>2\log |G|</tex>, а для вызываемых Next и Enum необходимо <tex>O(\log |G|)</tex> памяти.
  
Таким образом показано, что STNONCON ∈ NL.
+
Таким образом показано, что STNONCON ∈ NL. Поскольку STNONCON ∈ coNLC, то получаем, что любую задачу из coNLC можно свести к задаче из NL, а значит coNL<tex>\subset</tex>NL.
 +
Из соображений симметрии NL<tex>\subset</tex>coNL, а значит NL &nbsp;=&nbsp; coNL.

Версия 16:26, 15 апреля 2010

Теорема Иммермана

Утверждение теоремы

NL = coNL

Доказательство

Решим задачу STNONCON на логарифмической памяти и покажем, что STNONCON ∈ NL.

[math]\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon [/math] нет пути из [math]s[/math] в [math]t[/math] в графе [math]G\}.[/math]

Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий [math]O(\log n)[/math] памяти, который проверяет достижима ли вершина [math]t[/math] из [math]s[/math].

Чтобы показать правильность работы алгоритма необходимо показать:

  • В случае недостижимости [math]t[/math] из [math]s[/math] недетерминированые выборы приводят алгоритм к единице.
  • Если [math]t[/math] достижима из [math]s[/math], то вне зависимости от недетерминированых выбором, совершаемых алгоритмом, результат ноль.

Определим [math]R_i[/math]  =  {[math]v[/math]: существует путь из [math]s[/math] в [math]v[/math] длиной [math]\le i[/math]}. Другими словами это множество всех вершин, достижимых из [math]s[/math] не более чем за [math]i[/math] шагов. Обозначим [math]|R_i|[/math] за [math]r_i[/math]. Заметим, что если [math]t \notin R_{n-1}[/math], где [math]n[/math]  =  [math]|V|[/math], то не существует путь [math]s[/math] в [math]t[/math] в графе [math]G[/math], то есть [math]\lt G, s, t\gt \in \text{STNONCON}[/math].

Лемма: Можно построить недетерминированный алгоритм, который будет принимать верно заданное [math]r_i[/math] и при этом будет перечислять все вершины из [math]R_i[/math] на логарифмической памяти.

 Enum(s, i, r_i, G)
   counter := 0 //количество уже найденных и выведенных элементов
   for v = 1 .. n do //перебираем все вершины графа
     continue or find path //недетерминировано выбираем переходить к следующей вершине или угадываем путь до данной
     counter++ 
     yield return v //выдаем вершину, до которой угадали путь
     if counter ≥ r_i then //нашли r_i вершин, принимаем и завершаем работу
       ACCEPT
   REJECT //не нашли r_i вершин, отклоняем

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

Теперь имея [math]Enum[/math], можно индуктивно находить [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(s, i, r_i, G)
   r := 1 //[math]r_{i+1}[/math] хотя бы один, так как [math]s \in R_{i + 1}[/math]
   for v = 1 .. n; [math]v \neq s[/math] do //перебираем все вершины графа, кроме s -- это кандидаты на попадание в    [math]R_{i + 1}[/math]
     for u : (u,v)∈E do //перебираем все ребра, входящие в v
       Enum(s, i, r_i, G) //перечисляем все вершины из [math]R_i[/math]
       if u in output then //если u одна из них, то [math]v \in R_{i + 1}[/math]
         r++   //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата
         break
   write r

Данный алгоритм изначально учитывает [math]s[/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] и еще поочередно значения полученные в результате вызова [math]Enum[/math].

Теперь можно написать алгоритм, который будет недетерминировано решать задачу [math]STNONCON[/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] подставляется новое полученное значение.

 NONCON(G, s, t)
   [math]r_n[/math] := 1 //[math]r_0[/math]
   for i = 0..n-2 do //Вычисляем [math]r_{n - 1}[/math]
     [math]r_n[/math] := Next(s, i, [math]r_n[/math], G)
   Enum(s, n - 1, [math]r_n[/math], G) //Перечисляем вершины из [math]R_{n - 1}[/math]
   if t in output then //Если t была перечислена то t достижима и выдаем REJECT, иначе ACCEPT
     REJECT 
   else
     ACCEPT 

Данный алгоритм использует [math]O(\log |G|)[/math] памяти, так как для хранения [math]r_n[/math] и [math]i[/math] необходимо [math]2\log |G|[/math], а для вызываемых Next и Enum необходимо [math]O(\log |G|)[/math] памяти.

Таким образом показано, что STNONCON ∈ NL. Поскольку STNONCON ∈ coNLC, то получаем, что любую задачу из coNLC можно свести к задаче из NL, а значит coNL[math]\subset[/math]NL. Из соображений симметрии NL[math]\subset[/math]coNL, а значит NL  =  coNL.