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