Изменения

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

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

113 байт добавлено, 14:31, 6 апреля 2010
Нет описания правки
:<tex>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon </tex> нет пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G\}.</tex>
 
''R<sub>i</sub>''&nbsp;=&nbsp;{''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}
Чтобы показать, что STNONCON входит в NL, можно придумать недетерминированый алгоритм, использующий <tex>O(\log n)</tex> памяти, который
48
правок

Навигация