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