Теорема Иммермана — различия между версиями
Akhi (обсуждение | вклад) |
Akhi (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
:<tex>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon </tex> нет пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G\}.</tex> | :<tex>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon </tex> нет пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G\}.</tex> | ||
| − | |||
| − | |||
Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий <tex>O(\log n)</tex> памяти, который | Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий <tex>O(\log n)</tex> памяти, который | ||
| Строка 22: | Строка 20: | ||
достижимых из ''s'' не более чем за ''i'' шагов. Обозначим |''R<sub>i</sub>''| за ''r<sub>i</sub>''. | достижимых из ''s'' не более чем за ''i'' шагов. Обозначим |''R<sub>i</sub>''| за ''r<sub>i</sub>''. | ||
Заметим, что если <tex>t \notin R_{n-1}</tex>, где ''n'' = |''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON. | Заметим, что если <tex>t \notin R_{n-1}</tex>, где ''n'' = |''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON. | ||
| + | |||
| + | '''Лемма''': Можно построить алгоритм, который по данному ''r<sub>i</sub>'' будет перечислять все вершины из ''R<sub>i</sub>'' и удачно завершаться на логарифмической памяти. Если ''r<sub>i</sub>'' больше истинного размера ''R<sub>i</sub>'', | ||
| + | то алгоритм завершится неудачно; однако если ''r<sub>i</sub>'' меньше истинного размера ''R<sub>i</sub>'', то алгоритм завершится удачно, но перечислит лишь некое подмножество ''R<sub>i</sub>''. | ||
| + | |||
| + | <code> | ||
| + | Enum(s, i, r_i, G) | ||
| + | counter := 0 //''количество уже найденных и выведенных элементов'' | ||
| + | '''for''' v = 1 .. n '''do''' //''перебираем все вершины графа'' | ||
| + | ''continue or find path'' //''недетерминировано выбираем переходить к следующей вершине или угадываем путь до данной'' | ||
| + | counter++ | ||
| + | write v //''выводим вершину, до которой угадали путь'' | ||
| + | ''if'' counter ≥ r_i ''then'' //''нашли r_i вершин, удачно завершаем работу'' | ||
| + | ACCEPT | ||
| + | REJECT //''не нашли r_i вершин'' | ||
| + | </code> | ||
| + | |||
| + | Enum перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из ''s''. | ||
Версия 14:51, 6 апреля 2010
Теорема Иммермана
Утверждение теоремы
NL = coNL
Доказательство
Решим задачу STNONCON на логарифмической памяти.
- нет пути из в в графе
Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий памяти, который проверяет достижима ли вершина t из s.
Чтобы показать правильность работы алгоритма необходимо показать:
- В случае недостижимости t из s недетерминированые выборы приводят алгоритм к единице.
- Если t достижима из s, то вне зависимости от недетерминированых выбором, совершаемых алгоритмом, результат ноль.
Определим Ri = {v: существует путь из s в v длиной ≤ i}. Другими словами это множество всех вершин, достижимых из s не более чем за i шагов. Обозначим |Ri| за ri. Заметим, что если , где n = |V|, то не существует путь s в t в графе G, то есть ∈ STNONCON.
Лемма: Можно построить алгоритм, который по данному ri будет перечислять все вершины из Ri и удачно завершаться на логарифмической памяти. Если ri больше истинного размера Ri, то алгоритм завершится неудачно; однако если ri меньше истинного размера Ri, то алгоритм завершится удачно, но перечислит лишь некое подмножество Ri.
Enum(s, i, r_i, G)
counter := 0 //количество уже найденных и выведенных элементов
for v = 1 .. n do //перебираем все вершины графа
continue or find path //недетерминировано выбираем переходить к следующей вершине или угадываем путь до данной
counter++
write v //выводим вершину, до которой угадали путь
if counter ≥ r_i then //нашли r_i вершин, удачно завершаем работу
ACCEPT
REJECT //не нашли r_i вершин
Enum перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из s.
