Złożoność ścieżek zliczania na wykresie

Biorąc pod uwagę ukierunkowany wykres z n węzłami, tak że każdy wierzchołek ma dokładnie dwie krawędzie wychodzące, a liczbę naturalną N zakodowaną dwójkowo, dwa wierzchołki s i t,

Chcę policzyć liczbę (niekoniecznie prostych) ścieżek od s do t w obrębie N kroków.

Czy to trudny problem # P? Lub ogólnie, jaka jest złożoność tego problemu?

cc.complexity-theory graph-theory counting-complexity maomao
źródło

Próbowałeś zasilania matrycy?

Yuval Filmus

tak, ale o ile widzę, złożoność nie jest jeszcze znana.

maomao

Czy spacer musi się kończyć o t, czy po prostu odwiedzić t w którymś momencie?

Tyson Williams,

musi kończyć się na t.

maomao,

@Geekster Dla pełnego digrafu na 3 wierzchołkach z , liczba to N-ta liczba Fibonacciego, której wielkość jest wykładnicza w N, tak jak David argumentował w odpowiedzi na dowolny wykres.

s \neq t

$s \ne t$

Tyson Williams,

Odpowiedzi:

Wyjściowa liczba ścieżek może wynosić (wybierz dowolnie, a następnie wybierz jako wierzchołek, który jest punktem końcowym największej liczby spacerów od ), co wymaga $\Omega(2^N/n)$ $s$ $t$ $2^N$ $s$ $\Omega(N)$ bity do wyraźnego spisania; jest to wykładniczy rozmiar wejściowy. Z drugiej strony, podejście do zasilania macierzy ma wielomian złożoności w sumie wielkości wejściowych i wyjściowych. Wydaje się więc, że umieszcza to dokładnie w klasie problemów z liczeniem, które mają wyjściowy rozmiar wykładniczy i mogą być rozwiązane deterministycznie w wielomianu czasowym w wielkości wyjściowej, niezależnie od zapisu dla tej klasy (jest to pewien rodzaj liczenia analogiczny dla EXP i zdecydowanie nie #EXP, który jest bardziej analogiczny do NEXP).

David Eppstein
źródło

dzięki, ale nadal chcę wiedzieć, czy ten problem jest .

♯ P

$\sharp P$

maomao,

Aby uniknąć dużych liczb w iterowanym podejściu do kwadratu Davida, możemy wykonać wszystkie obliczenia modulo liczbą pierwszą p. Następnie cały algorytm działa w funkcji wielomianu czasowego w . Jeśli problem byłby trudny do uzyskania w przypadku P w przypadku wielomianowych skąpych redukcji w trybie wielomianowym, algorytm oznaczałby P = P, w co nie wierzymy.

n + \log N + \log p

$n + \log N + \log p$

p = 2

$p=2$

\oplus

$\oplus$

Holger

@Holger nie miałby podobnego argumentu dla Stałego? tzn. jeśli Permanent to # P-hard, to Perm mod 2 będzie P hard. Ale Perm mod 2 = Det mod 2, który jest w P.

\oplus

$\oplus$

SamiD

@SamiD: Dokładnie, twój argument pokazuje, że permanent nie jest prawdopodobnie # P-twardy przy skąpych redukcjach. Znane dowody wykorzystują redukcje Turinga.

Holger,

@Holger Zgadzam się. Przepraszam, że tęskniłem za skąpym, niejednokrotnie częścią. Tak więc problem z zasilaniem matrycy może być # P-trudny w warunkach redukcji Turinga.

SamiD,

Znalezienie gdzie jest macierzą przyległości danego wykresu, sprowadza się do problemu zdefiniowanego najpierw w [ABKPM], który ma ustaloną dolną granicę w tym samym artykule. Jednak to, czy redukcja w odwrotnym kierunku jest zachowana, tj. Od do problemu zasilania macierzy, jest otwarte AFAIK. $A^N[s,t]$ $A$ $\mathsf{BitSLP}$ $\#\mathsf{P}$ $\mathsf{BitSLP}$

Zauważ, że znajduje się dokładnie w hierarchii zliczania . Najbardziej znana górna granica tego problemu, a mianowicie. jest stąd . $\mathsf{BitSLP}$ $\mathsf{CH} \subseteq \mathsf{PSPACE}$ $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$

SamiD
źródło

Problem jest # P-ukończony. Spójrz na problem zliczania najkrótszych ścieżek na wykresie (ND31 w Garey & Johnson), który jest # P-zupełny dla wersji zliczającej. Przeczytaj uważnie komentarz. To daje odpowiedź na odcinkach o długości . Aby uzyskać odpowiedź na ścieżki o długości , wywołaj problem najkrótszych ścieżek dla i , a następnie odejmij ten drugi od pierwszego, tzn. Wykonaj odejmowanie redukcji. $\leq N$ $=N$ $\leq N$ $\leq N-1$

Ponieważ redukcja z #HAMILTONIAN PATHS / CIRCUITS do #SHORTEST PATHS działa również dla wykresów 3-regularnych, wynik # P-zupełności będzie działał również w przypadku ograniczenia digrafów z out- . $\leq 2$

Miki Hermann
źródło

Pierwotny problem nie wymaga prostej ścieżki, więc nie sądzę, aby odpowiedź była poprawna.

maomao,

Jak może być # P-complete, gdy wszystkie problemy #P mają liczbę rozwiązań wykładniczych pod względem wielkości wejściowej, a ten jest podwójnie wykładniczy?

David Eppstein,

Co oznacza „ND31” w kontekście książki Gareya i Johsona?

Tyson Williams,