Изменения

Перейти к: навигация, поиск

Теорема Иммермана

6 байт добавлено, 17:54, 15 апреля 2010
Нет описания правки
=== Утверждение теоремы ===
<tex>\text{NL} = \text{coNL}</tex>
(ffff)
=== Доказательство ===
Решим задачу <tex>\text{STNONCON}</tex> (''s-t non connectivity'') на логарифмической памяти и покажем, что <tex>\text{STNONCON} \in \text{NL}</tex>.
Анонимный участник

Навигация