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