Complexité des chemins de comptage dans un graphe

Étant donné un graphe orienté avec n nœuds tels que chaque sommet a exactement deux bords sortants, et un nombre naturel N codé en binaire, deux sommets s et t,

Je veux compter le nombre de chemins (pas nécessairement simples) de s à t dans N étapes.

Est-ce un problème # P-difficile? Ou généralement, quelle est la complexité de ce problème?

Le nombre de chemins de sortie peut être (choisissez arbitrairement, puis choisissez comme sommet qui est le point final du plus grand nombre des promenades de ) qui nécessites t 2 N s Ω ( N $\Omega(2^N/n)$$s$$t$$2^N$$s$$\Omega(N)$bits à écrire explicitement; c'est exponentiel dans la taille d'entrée. D'un autre côté, l'approche de mise sous tension matricielle a un polynôme de complexité dans la somme des tailles d'entrée et de sortie. Donc, cela semble le placer carrément dans la classe des problèmes de comptage qui ont une sortie de taille exponentielle et peuvent être résolus de manière déterministe dans le polynôme temporel dans leur taille de sortie, quelle que soit la notation de cette classe (c'est une sorte d'analogue de comptage pour EXP, et certainement pas #EXP qui est plus analogue à NEXP).

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

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

$\leq 2$