Теорема Иммермана — различия между версиями
Akhi (обсуждение | вклад) (Новая страница: «== Теорема Иммермана == === Утверждение теоремы === NL = coNL === Доказательство === Решим задачу STNONC…») |
Akhi (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
Определим ''R<sub>i</sub>'' = {''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}. Другими словами это множество всех вершин, | Определим ''R<sub>i</sub>'' = {''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'' = |''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON. | + | Заметим, что если ''t''<tex>$\notin$<\tex>''R''<sub>''n''−1</sub>, где ''n'' = |''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON. |
Версия 14:25, 6 апреля 2010
Теорема Иммермана
Утверждение теоремы
NL = coNL
Доказательство
Решим задачу STNONCON на логарифмической памяти.
Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий памяти, который проверяет достижима ли вершина 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, то есть ∈ STNONCON.
