48
правок
Изменения
Нет описания правки
:<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> памяти, который
достижимых из ''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.
'''Лемма''': Можно построить алгоритм, который по данному ''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''.
