Сложность уникального st-Connectivity

Я хотел бы знать, может ли быть решена следующая проблема в (недетерминированное пространство журнала):$\mathsf{NL}$

Для ориентированного графа с двумя выделенными вершинами s и t существует ли единственный путь из s в t в G ?s $G$$s$$t$т $s$$t$$G$

Я чувствую, что он, вероятно, находится в $\mathsf{NL}$ так как мы можем решить, есть ли путь $s$ - $t$ и нет ли такого пути. Тем не менее, подсчет количества таких путей является $\mathsf{\sharp P}$ -hard (Valiant, 1979).

Итак, мои вопросы: у вас есть ссылки на это? Очевидно ли, что он находится в $\mathsf{NL}$ ? Или это не в $\mathsf{NL}$ ?

Кажется, ваша проблема в $NL$ . Вот алгоритм.

Во-первых, недетерминированно угадать путь от $s$ до $t$ . Если вы угадаете неправильно, отклоните . Назовите этот алгоритм $A$ .

Рассмотрим следующий недетерминированный алгоритм , который определяет, существуют ли хотя бы два пути. Учитывая граф и , для всех пар различных ребер угадать путь от до который включает но не , затем угадать путь от до который включает но не . Если догадки верны, примите . Если для всех вариантов и не принято ни одного подтверждения , отклоните . Примечание реализуемо в недетерминированном пространстве журнала.сек , т е , е с т е е с т е е е е $B$$s,t$$e,f$$s$$t$$e$$f$$s$$t$$f$$e$$e$$f$$B$

Теперь множество - это множество - графов, по крайней мере с двумя путями из в . Поскольку , дополнение также в , то есть, мы можем определить, и иметь меньше , чем два пути, в недетерминированных logspace.s t s t N L = c o N L B N L s $L(B)$$s$$t$$s$$t$$NL = coNL$$B$$NL$$s$$t$

Последний алгоритм: «Запустите Если принимает, запустите дополнение и выведите его ответ».A $A$$A$$B$

Я не знаю ссылки.

ОБНОВЛЕНИЕ: Если вы действительно хотите ссылку, ознакомьтесь с первым параграфом Раздела 3 этого документа . Но это, вероятно, только одна из многих ссылок, которые ссылаются на это следствие. Было бы более разумно назвать результат "фольклором", а не ссылаться на статью, в которой упоминается об этом.

ОБНОВЛЕНИЕ 2: Предположим, вы хотите определить, существует ли уникальный простой путь. В этом случае алгоритм не должен изменяться: если путь вообще существует, тогда существует простой путь. Я считаю , что следующая модификация будет работать для алгоритма .$A$$B$

Мы хотим переписать алгоритм так, чтобы он принимал, если есть хотя бы два простых пути.$B$

Сначала рассмотрим следующий алгоритм полиномиального времени для задачи. Найти кратчайший путь от до . Для каждого ребра в проверьте, существует ли другой путь - , который не проходит через . Если вы найдете такой путь, то примите . Если вы никогда не найдете другой путь, то отклоните . Поскольку является самым коротким, у него нет цикла, и если есть другой путь, который не использует какое-либо ребро , то есть другой путь, который прост и не использует какое-то ребросек т е р сек т е Р Р $P$$s$$t$$e$$P$$s$$t$$e$$P$$P$$P$, (Этот алгоритм используется для решения проблемы «вторых кратчайших путей».)

Мы будем реализовывать этот алгоритм в . Если бы у нас был алгоритм для запроса ребер в фиксированном пути , мы могли бы реализовать вышеизложенное в недетерминированном логарифмическом пространстве: перебирая все ребра в , угадывая путь - и проверяя его для каждого ребра, посещенного по пути , ни один из них не равен .N L E P e P s t $NL$$NL$$e$$P$$e$$P$$s$$t$$e$

Итак, нам нужен «оракул пути», алгоритм со свойством: учитывая , в каждом пути вычислений алгоритм либо сообщает й фронт на конкретном фиксированном пути - , либо отказаться . Мы можем получить путь оракула, используя чтобы выделить лексикографически первый путь.i = 1 , … , n i s t N L = c o N $NL$$i=1,\ldots,n$$i$$s$$t$$NL=coNL$

Вот набросок пути оракула.

Найдите , длину кратчайшего пути от до , попробовав все и используя .s t k = 1 , … , n N L = c o N $k$$s$$t$$k=1,\ldots,n$$NL=coNL$

Установите переменные , , .x : = 1 j : = $u:=s$$x:=1$$j:=k$

Для всех соседей из в лексикографическом порядке,$v$$u$

Определите, существует ли путь от до длины (используя результат ). Точнее, запустить недетерминированную алгоритм - связи (длины ) и алгоритм его дополнения, одновременно. Когда один из них принимает, идите с его ответом (он должен быть правильным; оба не могут принять). Если оба отклоняют, то отклоняют .t j - 1 N L $v$$t$$j-1$$NL=coNL$$s$$t$$j-1$

Если пути нет, переходите к следующему соседу. Если вы исчерпали всех соседей, откажитесь .

Если есть путь, то, если , выведите в качестве го ребра на пути от до . В противном случае увеличьте , уменьшите , установите и снова запустите цикл for, если .( u , v ) i s t x j u : = v v ≠ $x=i$$(u,v)$$i$$s$$t$$x$$j$$u := v$$v \neq t$

Если после достижения вывод плохой (заданный был слишком большим).т I$x < i$$t$$i$$i$

Учитывая , этот алгоритм либо выводит е ребро по лексикографически кратчайшему пути из в , либо отклоняет.я P S $i$$i$$P$$s$$t$