Jak trudno policzyć liczbę prostych ścieżek między dwoma węzłami na ukierunkowanym wykresie?

Istnieje prosty algorytm wielomianowy, który decyduje, czy istnieje ścieżka między dwoma węzłami na ukierunkowanym wykresie (po prostu wykonaj rutynowe przemierzanie wykresu za pomocą, powiedzmy, głębokości pierwszego wyszukiwania).

Jednak wydaje się, że, co zaskakujące, problem staje się znacznie trudniejszy, jeśli zamiast testowania istnienia chcemy policzyć liczbę ścieżek.

Jeśli pozwolimy wierzchołków ścieżki do ponownego wykorzystania, a następnie istnieje rozwiązanie programowanie dynamiczne, aby znaleźć liczbę ścieżek z s do t o n krawędziach. Jeśli jednak zezwolimy tylko na proste ścieżki, które nie wykorzystują ponownie wierzchołków, jedynym rozwiązaniem, o którym mogę pomyśleć, jest wyliczenie ścieżek metodą brute force , co ma wykładniczą złożoność czasową.

Więc pytam,

• Czy trudno jest policzyć liczbę prostych ścieżek między dwoma wierzchołkami?
• Jeśli tak, to czy jest to rodzaj NP-complete? (Mówię trochę, ponieważ technicznie nie jest to problem decyzyjny ...)
• Czy są też inne problemy w P, które mają takie trudne wersje? **

Najczęstszą klasą złożoności związaną z liczeniem problemów jest #P . Decyzja, czy istnieje prosta ścieżka z danego węzła do drugiego, jest wyraźnie podana w NP. Liczenie ich jest następnie w #P.

$n!$

Odpowiedź na dwa pierwsze dwa pytania brzmi: tak, jest trudna, jest to # P-complete (ref) .

Wikipedii artykuł daje istotne fakty: 1) algorytmy probabilistyczne są przydatne do przybliżona # funkcji P-kompletne, a to rodzaj algorytmu wykorzystywane do zbliżenia w poprzednim artykule. 2) Istnieją inne łatwe problemy z trudnymi (# P-zupełnymi) wersjami liczenia:

• znajdowanie (liniowe) vs. zliczanie wszystkich zadań spełniających formułę DNF lub wystąpienie 2-SAT
• znajdowanie (liniowe) vs. zliczanie sortowań topologicznych
• znajdowanie (O (VE)) vs. liczenie idealnego dopasowania na grafach dwustronnych

Wiesz już, że jeśli usuniesz ograniczenie „prosta ścieżka”, problem wpada w P (cóż, musisz ograniczyć długość ścieżek przez wielomian wielkości wykresu lub podać granicę w sposób jednoznaczny)