48
правок
Изменения
Новая страница: «== Теорема Иммермана == === Утверждение теоремы === NL = coNL === Доказательство === Решим задачу STNONC…»
== Теорема Иммермана ==
=== Утверждение теоремы ===
NL = coNL
=== Доказательство ===
Решим задачу STNONCON на логарифмической памяти.
:<math>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon \text{ нет пути из }s\text{ в }t\text{ в графе }G\}.</math>
Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий <tex>O(\log n)</tex> памяти, который
проверяет достижима ли вершина ''t'' из ''s''.
Чтобы показать правильность работы алгоритма необходимо показать:
*В случае недостижимости ''t'' из ''s'' недетерминированые выборы приводят алгоритм к единице.
*Если ''t'' достижима из ''s'', то вне зависимости от недетерминированых выбором, совершаемых алгоритмом, результат ноль.
Определим ''R<sub>i</sub>'' = {''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}. Другими словами это множество всех вершин,
достижимых из ''s'' не более чем за ''i'' шагов. Обозначим |''R<sub>i</sub>''| за ''r<sub>i</sub>''.
Заметим, что если ''t''<tex>\notin<\tex>''R''<sub>''n''−1</sub>, где ''n'' = |''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON.
=== Утверждение теоремы ===
NL = coNL
=== Доказательство ===
Решим задачу STNONCON на логарифмической памяти.
:<math>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon \text{ нет пути из }s\text{ в }t\text{ в графе }G\}.</math>
Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий <tex>O(\log n)</tex> памяти, который
проверяет достижима ли вершина ''t'' из ''s''.
Чтобы показать правильность работы алгоритма необходимо показать:
*В случае недостижимости ''t'' из ''s'' недетерминированые выборы приводят алгоритм к единице.
*Если ''t'' достижима из ''s'', то вне зависимости от недетерминированых выбором, совершаемых алгоритмом, результат ноль.
Определим ''R<sub>i</sub>'' = {''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}. Другими словами это множество всех вершин,
достижимых из ''s'' не более чем за ''i'' шагов. Обозначим |''R<sub>i</sub>''| за ''r<sub>i</sub>''.
Заметим, что если ''t''<tex>\notin<\tex>''R''<sub>''n''−1</sub>, где ''n'' = |''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON.
