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