Complexidade da contagem de caminhos em um gráfico

12

Dado um gráfico direcionado com n nós, de modo que cada vértice tenha exatamente duas arestas de saída e um número natural N codificado em binário, dois vértices s e t,

Quero contar o número de caminhos (não necessariamente simples) de s a t em N etapas.

Este é um problema # P-difícil? Ou, geralmente, qual é a complexidade desse problema?

maomao
fonte
6
Você tentou ligar a matriz?
Yuval Filmus
1
sim, mas a complexidade ainda não é conhecida, tanto quanto eu posso ver.
maomao 30/07/12
A caminhada precisa terminar em t ou apenas visitar t em algum momento da caminhada?
Tyson Williams
tem que acabar em t.
maomao 6/08/12
1
@Geekster Para o dígrafo completa em 3 vértices com , a contagem é o número Nth Fibonacci, cujo tamanho é exponencial em N, assim como David argumentou em sua resposta para qualquer gráfico. st
Tyson Williams

Respostas:

13

O número de saída dos caminhos pode ser (escolha s arbitrariamente e escolha t como o vértice que é o ponto final do maior número de 2 N caminhadas de s ) que requer Ω ( N )Ω(2N/n)st2NsΩ(N)bits para escrever explicitamente; isso é exponencial no tamanho da entrada. Por outro lado, a abordagem de alimentação da matriz possui polinômio de complexidade na soma dos tamanhos de entrada e saída. Portanto, isso parece colocá-lo diretamente na classe de problemas de contagem que têm saída de tamanho exponencial e podem ser resolvidos deterministicamente no polinômio do tempo em seu tamanho de saída, independentemente da notação dessa classe (é algum tipo de contagem analógica para EXP, e definitivamente não é o #EXP, que é mais análogo ao NEXP).

David Eppstein
fonte
1
obrigado, mas ainda quero saber se esse problema é duro. P
maomao 6/08/12
1
Para evitar os grandes números na abordagem quadrática iterada de David, podemos fazer todo o módulo de computação um número primo p. Então o algoritmo geral é executado no polinômio do tempo em . Se o problema fosse # P-difícil sob reduções parcimoniais numerosas de um polinômio, o algoritmo com p = 2 implicaria P = P, o que não acreditamos. n+logN+logpp=2
Holger
@SamiD: Exatamente, seu argumento mostra que a permanente provavelmente não é # P-hard sob reduções parcimoniosas . As provas conhecidas usam reduções de Turing.
Holger
@ Hollger, eu concordo. Desculpe, eu tinha perdido a parcimoniosa parte múltipla . Portanto, o problema de alimentação da matriz pode ser # P-rígido sob reduções de Turing.
SamiD 02/12/15
4

AN[s,t]ABitSLP#PBitSLP

BitSLPCHPSPACEPHPPPPPP

SamiD
fonte
1

N=NNN1

2

Miki Hermann
fonte
2
O problema original não exige que o caminho seja simples, portanto, não acho que a resposta esteja correta.
maomao 6/08/12
3
Como pode ser # P-completo quando todos os problemas de # P têm um número de soluções exponenciais no tamanho da entrada e essa é dupla exponencial?
David Eppstein
O que significa "ND31" no contexto do livro de Garey e Johson?
Tyson Williams