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>
