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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
Определим ''R<sub>i</sub>''&nbsp;=&nbsp;{''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}. Другими словами это множество всех вершин,
 
Определим ''R<sub>i</sub>''&nbsp;=&nbsp;{''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}. Другими словами это множество всех вершин,
 
достижимых из ''s'' не более чем за ''i'' шагов. Обозначим |''R<sub>i</sub>''| за ''r<sub>i</sub>''.
 
достижимых из ''s'' не более чем за ''i'' шагов. Обозначим |''R<sub>i</sub>''| за ''r<sub>i</sub>''.
Заметим, что если ''t''<tex>$\notin$<\tex>''R''<sub>''n''−1</sub>, где ''n''&nbsp;=&nbsp;|''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON.
+
Заметим, что если ''t'' <tex>\notin<\tex> ''R''<sub>''n''−1</sub>, где ''n''&nbsp;=&nbsp;|''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON.

Версия 14:25, 6 апреля 2010

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

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

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, можно придумать недетерминированый алгоритм, использующий [math]O(\log n)[/math] памяти, который проверяет достижима ли вершина t из s.

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

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

Определим Ri = {v: существует путь из s в v длиной ≤ i}. Другими словами это множество всех вершин, достижимых из s не более чем за i шагов. Обозначим |Ri| за ri. Заметим, что если t <tex>\notin<\tex> Rn−1, где n = |V|, то не существует путь s в t в графе G, то есть [math]\langle G,s,t\rangle[/math] ∈ STNONCON.