48
правок
Изменения
Нет описания правки
Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий <tex>O(\log n)</tex> памяти, который
проверяет достижима ли вершина ''<tex>t'' </tex> из ''<tex>s''</tex>.
Чтобы показать правильность работы алгоритма необходимо показать:
*В случае недостижимости ''<tex>t'' </tex> из ''<tex>s'' </tex> недетерминированые выборы приводят алгоритм к единице.*Если ''<tex>t'' </tex> достижима из ''<tex>s''</tex>, то вне зависимости от недетерминированых выбором, совершаемых алгоритмом, результат ноль.
Определим ''R<subtex>iR_i</subtex>'' = {''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}. Другими словами это множество всех вершин,
достижимых из ''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.
