Сложность подсчета путей в графе

Дан ориентированный граф с n узлами, такими, что каждая вершина имеет ровно два исходящих ребра, и натуральное число N, закодированное в двоичном виде, две вершины s и t,

Я хочу посчитать количество (не обязательно простых) путей от s до t в течение N шагов.

Это # P-сложная проблема? Или вообще, в чем сложность этой проблемы?

cc.complexity-theory graph-theory counting-complexity Maomao
источник

Вы пробовали питание матрицы?

Юваль Фильмус

да, но сложность до сих пор не известна, насколько я вижу.

Maomao

Должна ли прогулка заканчиваться в t или просто посетить t в какой-то момент прогулки?

Тайсон Уильямс

это должно закончиться в т.

Maomao

@Geekster Для полного орграфа на 3 вершинах с счетом является N-е число Фибоначчи, размер которого экспоненциально по N, так же, как Дэвид утверждал в своем ответе для любого графа.

s \neq t

$s \ne t$

Тайсон Уильямс

Ответы:

Выходное число путей может быть (выберите произвольно, а затем выберите в качестве вершины, которая является конечной точкой наибольшего числа прогулок из ), для которого требуется $\Omega(2^N/n)$ $s$ $t$ $2^N$ $s$ $\Omega(N)$ биты для записи в явном виде; это экспоненциально в размере ввода. С другой стороны, подход питания матрицы имеет многочлен сложности по сумме входных и выходных размеров. Так что это, кажется, помещает это прямо в класс подсчета проблем, которые имеют выход экспоненциального размера и могут быть решены детерминистически по полиному времени по их размеру вывода, какой бы ни была запись для этого класса (это своего рода аналог подсчета для EXP, и определенно не #EXP, который более аналогичен NEXP).

Дэвид Эппштейн
источник

спасибо, но я все еще хочу знать, является ли эта проблема .

♯ P

$\sharp P$

Maomao

Чтобы избежать больших чисел в методе повторного возведения в квадрат Дэвида, мы можем выполнять все вычисления по модулю простого числа p. Тогда общий алгоритм выполняется по полиному времени от . Если бы проблема была # P-трудной при многократном сокращении за полиномиальное время, алгоритм с подразумевал бы P = P, в который мы не верим.

n + \log N + \log p

$n + \log N + \log p$

p = 2

$p=2$

\oplus

$\oplus$

Хольгер

@ Хольгер, неужели подобный аргумент не будет иметь место для Перманента? то есть, если Permanent является # P-hard, то Perm mod 2 будет P hard. Но Perm mod 2 = Det mod 2, который есть в P.

\oplus

$\oplus$

SamiD

@SamiD: Точно, ваш аргумент показывает, что перманент, вероятно, не # P-hard при скупых сокращениях. Известные доказательства используют сокращения Тьюринга.

Хольгер

@ Хольгер, я согласен. Извините, я пропустил скупую много-одну часть. Таким образом, проблема питания матрицы может быть очень сложной при сокращениях по Тьюрингу.

SamiD

Нахождение бита где - матрица смежности данного графа, сводится к задаче определенной сначала в [ABKPM], для которой установлена нижняя граница в той же газете. Однако ли сокращение в обратном направлении, то есть с на проблему питания матрицы, открытым AFAIK. $A^N[s,t]$ $A$ $\mathsf{BitSLP}$ $\#\mathsf{P}$ $\mathsf{BitSLP}$

$\mathsf{BitSLP}$ $\mathsf{CH} \subseteq \mathsf{PSPACE}$ $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$

SamiD
источник

$\leq N$ $=N$ $\leq N$ $\leq N-1$

$\leq 2$

Мики Герман
источник

Первоначальная проблема не требует, чтобы путь был простым, поэтому я не думаю, что ответ правильный.

Maomao

Как это может быть # P-complete, если у всех #P задач есть числа решений, которые являются экспоненциальными по размеру ввода, а эта двойная экспонента?

Дэвид Эппштейн

Что означает «ND31» в контексте книги Гэри и Джонсона?

Тайсон Уильямс