Савич дал детерминированный алгоритм для решения проблемы st-связности, используя пространство , подразумевая . Алгоритм Савича выполняется за время . Это большая открытая проблема, может ли st-связность быть решена детерминированным алгоритмом за полиномиальное время и в O ({\ log} ^ 2 {n}) пространстве, т. Е. NL \ subseteq SC ^ 2 . RL , который лежит между L и NL , известен в SC ^ 2 . Следовательно, достижимость в ориентированных графах с полиномиальным временем смешивания находится в SC ^ 2 .N L ⊆ D S P A C E ( log 2 n ) 2 O ( log 2 n ) O ( log 2 n ) N L ⊆ S C 2 R L L N L S C 2
Я ищу особые случаи st-связности (которые, как известно, не в ), которые имеют алгоритмы . Что-нибудь известно о планарных графах, планарных DAG? Обратите внимание, что st-связность в группах обеспечения доступности баз данных остается NL-полной.
источник
Последняя сложная конференция показала некоторый прогресс в этом вопросе. Достижимость в планарных DAG с источниками может быть решена в пространствеO ( журналн ) O ( журналн ) .
Вот также недавний опрос Аллендер: «Проблемы с доступностью: обновление»
источник