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

Определение:

Задача несуществования пути между двумя заданными вершинами в данном графе [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]