48
правок
Изменения
Нет описания правки
:<tex>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon </tex> нет пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G\}.</tex>
:''R<sub>i</sub>'' = {''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}
Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий <tex>O(\log n)</tex> памяти, который
