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

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

[math]\text{NL} = \text{coNL}[/math]

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

Решим задачу [math]\text{STNONCON}[/math] (s-t non connectivity) на логарифмической памяти и покажем, что .

нет пути из в в графе

Чтобы показать, что [math]\text{STNONCON}[/math] входит в [math]\text{NL}[/math], можно придумать недетерминированый алгоритм, использующий [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 = \{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 = |V|[/math], то не существует путь [math]s[/math] в [math]t[/math] в графе [math]G[/math], то есть .

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


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

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

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

Теперь можно написать алгоритм, который будет недетерминировано решать задачу [math]\text{STNONCON}[/math] на логарифмической памяти. Он будет состоять из двух частей: вычисление [math]r_{n-1}[/math] и перечисление всех вершин из [math]R_{n - 1}[/math]. Вычисление [math]r_{n-1}[/math] происходит путем вызова [math]\text{Next}[/math] [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)
   //Перечисляем вершины из [math]R_{n - 1}[/math]
   if t in Enum(s, n - 1, [math]r_n[/math], G) 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], а для вызываемых [math]\text{Next}[/math] и [math]\text{Enum}[/math] необходимо [math]O(\log |G|)[/math] памяти.

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

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