Complejidad de contar caminos en un gráfico

Dado un gráfico dirigido con n nodos de modo que cada vértice tenga exactamente dos bordes salientes, y un número natural N codificado en binario, dos vértices syt,

Quiero contar el número de rutas (no necesariamente simples) de sa t en N pasos.

¿Es este un problema difícil de # P? O, en general, ¿cuál es la complejidad de este problema?

cc.complexity-theory graph-theory counting-complexity maomao
fuente

¿Intentaste alimentar la matriz?

Yuval Filmus

Sí, pero la complejidad aún no se conoce hasta donde puedo ver.

maomao

¿La caminata tiene que terminar en t o simplemente visitar t en algún momento de la caminata?

Tyson Williams el

tiene que terminar en t.

maomao

@Geekster Para el dígrafo completo en 3 vértices con

, el recuento es el enésimo número de Fibonacci, cuyo tamaño es exponencial en N, tal como David ha argumentado en su respuesta para cualquier gráfico.

s \neq t

$s \ne t$

Tyson Williams el

Respuestas:

El número de rutas de salida puede ser (elija arbitrariamente y luego elija como el vértice que es el punto final del mayor número de camina desde ) que requiere $\Omega(2^N/n)$ $s$ $t$ $2^N$ $s$ $\Omega(N)$ bits para escribir explícitamente; Esto es exponencial en el tamaño de entrada. Por otro lado, el enfoque de alimentación de matriz tiene un polinomio de complejidad en la suma de los tamaños de entrada y salida. Entonces, eso parece ubicarlo directamente en la clase de problemas de conteo que tienen una salida de tamaño exponencial y pueden resolverse de manera determinista en el tiempo polinomial en su tamaño de salida, sea cual sea la notación para esa clase (es una especie de análogo de conteo para EXP, y definitivamente no #EXP, que es más análogo a NEXP).

David Eppstein
fuente

gracias, pero todavía quiero saber si este problema es

-hard.

♯ P

$\sharp P$

maomao

Para evitar los grandes números en el enfoque de cuadratura iterativa de David, podemos hacer todos los módulos de cálculo un número primo p. Luego, el algoritmo general se ejecuta en tiempo polinomial en

. Si el problema era # P-duro bajo reducciones parsimoniosas de tiempo polinómico, el algoritmo con

implicaría P =

P, lo cual no creemos.

n + \log N + \log p

$n + \log N + \log p$

p = 2

$p=2$

\oplus

$\oplus$

Holger

@Holger, ¿no se mantendría un argumento similar para el Permanente? es decir, si permanente es # P-hard, entonces Perm mod 2 sería

P hard. Pero Perm mod 2 = Det mod 2 que está en P.

\oplus

$\oplus$

SamiD

@SamiD: Exactamente, su argumento muestra que el permanente probablemente no es # P-duro bajo reducciones parsimoniosas . Las pruebas conocidas utilizan reducciones de Turing.

Holger

@ Holger estoy de acuerdo. Lo siento, me había perdido la parte parsimoniosa de muchos . Por lo tanto, el problema de alimentación de la matriz puede ser muy difícil en las reducciones de Turing.

SamiD

$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
fuente

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

$\leq 2$

Miki Hermann
fuente

El problema original no requiere que la ruta sea simple, por lo que no creo que la respuesta sea correcta.

maomao

¿Cómo puede ser # P-completo cuando todos los problemas #P tienen un número de soluciones que son exponenciales en el tamaño de entrada y este es doblemente exponencial?

David Eppstein

¿Qué significa "ND31" en el contexto del libro de Garey y Johson?

Tyson Williams el