SC ^ 2 алгоритмы для st-связности

15

Савич дал детерминированный алгоритм для решения проблемы 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О(журнал2N)NLDSпAСЕ(журнал2N)2О(журнал2N)О(журнал2N)NLSС2рLLNL S C 2SС2SС2

Я ищу особые случаи st-связности (которые, как известно, не в L ), которые имеют алгоритмы SС2 . Что-нибудь известно о планарных графах, планарных DAG? Обратите внимание, что st-связность в группах обеспечения доступности баз данных остается NL-полной.

Шива Кинтали
источник

Ответы:

10

В \ text {NL} есть два связанных класса сложности, NLкоторые также находятся в LogDCFL , что помещает их в SC2 (автор Cook ).

  • Первый - RUL , для "Reach-Unigiguous Log-space", который имеет достижимость в мангровых зарослях (графы, где каждая пара вершин имеет не более одного направленного пути между ними) как полная проблема. Этот класс обсуждался ранее .
  • Вторым является ReachFewL , который имеет достижимость, полную для графов с не более чем полиномиальным числом путей между любой парой вершин.

Выполнение поиска в глубину на этих графах с использованием стека гарантирует, что это займет полиномиальное время, поэтому эти классы находятся в LogDCFLЮжная Каролина2 .

Деррик Стоули
источник
@ Деррик: Пожалуйста, добавьте ссылки, показывающие, что эти проблемы в LogDCFL.
Шива Кинтали
@Shiva: я думал, что последний параграф был аргументом, что эти проблемы могут быть признаны детерминированным автоматом понижения, определенным графом?
Андрас Саламон
1
@ Деррик: Спасибо. Таким образом, существуют проблемы в пересечении NL и LogDCFL, которые, как известно, не находятся в Logspace. Интересный !!
Шива Кинтали
2
Да, очень интересно. Опять же, мангровые заросли имеют (log log n) коэффициент эффективности пространства по сравнению с границей савича, но я не знаю подобной границы для графиков ReachFewL.
Деррик Столи
1
Новости из COCOON'11: Теперь является равным . Woohoo! Р е с ч U LреaсчасFевесL реaсчасUL
Сянь-Чи Чанг 之 之
9

Последняя сложная конференция показала некоторый прогресс в этом вопросе. Достижимость в планарных DAG с источниками может быть решена в пространствеО(журналN)О(журналN) .

Вот также недавний опрос Аллендер: «Проблемы с доступностью: обновление»

Райан Уильямс
источник
Похоже, что ни одна из «промежуточных» проблем (кроме RL) не известна в SC ^ 2.
Шива Кинтали