Złożoność liczenia prostych ścieżek na ukierunkowanym wykresie

Niech $G$ będzie cyfrą (niekoniecznie DAG) i niech . Co jest złożoność zliczania liczby prostych ścieżek . $s,t \in V(G)$ $s-t$$G$

Spodziewałbym się, że problemem będzie # -kompletny, ale nie udało mi się znaleźć dokładnego odwołania. ${\mathsf P}$

Zauważ również, że na wiele podobnych pytań udzielono poprawnych odpowiedzi tutaj i gdzie indziej, ale nie na to dokładne pytanie - aby podkreślić, że nie jestem zainteresowany liczeniem spacerów i / lub niekierowanych wykresów (w pierwszym przypadku wariant znajduje się w i w drugim # -hard).${\mathsf P}$${\mathsf P}$

Dowód kompletności # P zliczania prostych ścieżek st na wykresach niekierowanych i ukierunkowanych można znaleźć w:

Leslie G. Valiant: Złożoność problemów z liczeniem i rzetelnością . SIAM J. Comput. 8 (3): 410–421 (1979)

Z gazety:

$G; s,t \in V$
$s$$t$