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?
Respostas:
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) s t 2N s Ω(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).
fonte
fonte
fonte