Złożoność unikalnej łączności st

Chciałbym wiedzieć, czy w (niedeterministyczny obszar logów) można rozstrzygnąć następujący problem :$\mathsf{NL}$

Biorąc pod uwagę ukierunkowany wykres z dwoma wyróżnionymi wierzchołkami s i t , czy istnieje unikalna ścieżka od s do t w G ?$G$$s$$t$$s$$t$$G$

Czuję, że to może być w ponieważ możemy zdecydować, zarówno jeśli istnieje s - t -path, a jeśli nie ma takiej ścieżki. Jednak policzenie liczby takich ścieżek to ♯ P- twardy (Valiant, 1979).$\mathsf{NL}$$s$$t$$\mathsf{\sharp P}$

Więc moje pytania: Czy masz na ten temat referencje? Jest to oczywiste, że jest w ? Albo, że nie jest w N L ?$\mathsf{NL}$$\mathsf{NL}$

Wygląda na to, że twój problem . Oto algorytm.$NL$

Po pierwsze, niedeterministycznie odgadnij ścieżkę od do t . Jeśli zgadniesz niepoprawnie, odrzuć . Nazywamy to algorytm A .$s$$t$$A$

Rozważ następujący niedeterministyczny algorytm , który określa, czy istnieją co najmniej dwie ścieżki. Biorąc pod uwagę wykres i s , t , dla wszystkich par odrębnych krawędzi e , f , odgadnij ścieżkę od s do t, która zawiera e, ale nie f , a następnie odgadnij ścieżkę od s do t, która zawiera f, ale nie e . Jeśli domysły są prawidłowe, zaakceptuj . Jeśli nie nastąpi akceptacja wszystkich wyborów e i f , odrzuć . Uwaga $B$$s,t$$e,f$$s$$t$$e$$f$$s$$t$$f$$e$$e$$f$$B$ jest implementowalny w niedeterministycznym obszarze logów.

Teraz zestaw jest zbiorem wykresów s - t z co najmniej dwiema ścieżkami od s do t . Ze względu N L = C O N L , uzupełnieniem B jest również N L , a więc, można określić, czy y i T mają mniej niż dwie ścieżki, na niedeterministycznych logspace.$L(B)$$s$$t$$s$$t$$NL = coNL$$B$$NL$$s$$t$

Ostatnim algorytmem jest: „Uruchom Jeśli A akceptuje, uruchom dopełnienie B i wyślij odpowiedź”.$A$$A$$B$

Nie znam referencji.

AKTUALIZACJA: Jeśli naprawdę potrzebujesz referencji, zapoznaj się z pierwszym akapitem sekcji 3 tego dokumentu . Ale to prawdopodobnie tylko jedna z wielu referencji, które przytaczają tę konsekwencję. Bardziej rozsądne byłoby nazywanie wyniku „folklorem” niż cytowanie artykułu, który by o nim wspominał.

AKTUALIZACJA 2: Załóżmy, że chcesz ustalić, czy istnieje unikalna prosta ścieżka. W takim przypadku algorytm nie musi się zmieniać: jeśli w ogóle istnieje ścieżka, to istnieje prosta ścieżka. Wierzę, że po zmianach będzie pracować dla algorytmu B .$A$$B$

Chcemy przepisać algorytm aby akceptował iff, istnieją co najmniej dwie proste ścieżki.$B$

Najpierw rozważ następujący algorytm czasu wielomianowego dla problemu. Znajdź najkrótszą ścieżkę od s do t . Dla każdej krawędzi e w P sprawdź, czy istnieje inna ścieżka s - t , która nie przechodzi przez e . Jeśli znajdziesz taką ścieżkę, zaakceptuj . Jeśli nigdy nie znajdziesz innej ścieżki, odrzuć . Ponieważ P jest najkrótszy, nie ma cyklu, a jeśli istnieje inna ścieżka, która nie korzysta z krawędzi P , istnieje inna ścieżka, która jest prosta i nie używa krawędzi $P$$s$$t$$e$$P$$s$$t$$e$$P$$P$$P$. (Ten algorytm jest stosowany w przypadku problemu „drugiej najkrótszej ścieżki”).

Będziemy realizować ten algorytm w . Jeśli miało N L algorytm odpytywanie krawędzie e w ustalonej ścieżki P , można wdrażać powyższe niedeterministycznych logspace: iteracja wszystkich krawędziach e w P , odgadnąć e s - t drogi i sprawdzenia, że dla każdej krawędzi odwiedzanej wzdłuż sposób, żaden z nich nie jest równy e .$NL$$NL$$e$$P$$e$$P$$s$$t$$e$

Więc to, czego potrzebujemy jest „ścieżka oracle” An algorytm z właściwością: podane i = 1 , ... , n , w każdej ścieżce obliczeń algorytm albo zgłasza í th przewagę nad konkretnym ustalonym y - t ścieżce, lub odrzucić . Możemy uzyskać wyrocznię ścieżki, używając N L = c o N L do izolowania pierwszej ścieżki leksykograficznej.$NL$$i=1,\ldots,n$$i$$s$$t$$NL=coNL$

Oto szkic ścieżki wyroczni.

Znaleźć , długość najkrótszej drodze z S na T , próbując wszystkie k = 1 , ... , n i stosując N L = c o, N l .$k$$s$$t$$k=1,\ldots,n$$NL=coNL$

Ustaw zmienne , x : = 1 , j : = k .$u:=s$$x:=1$$j:=k$

Dla wszystkich sąsiadów z U w porządku leksykograficznym,$v$$u$

Ustal, czy istnieje ścieżka od do t o długości j - 1 (używając wyniku N L = c o N L ). Mówiąc dokładniej, uruchom jednocześnie algorytm niedeterministyczny dla połączenia s - t (o długości j - 1 ) i algorytm jego uzupełnienia. Gdy jeden z nich zaakceptuje, przejdź do jego odpowiedzi (musi być poprawna; obie nie mogą zaakceptować). Jeśli oba odrzucają, to odrzucają .$v$$t$$j-1$$NL=coNL$$s$$t$$j-1$

Jeśli nie ma ścieżki, przejdź do następnego sąsiada. Jeśli wyczerpałeś wszystkich sąsiadów, odrzuć je .

Jeśli istnieje ścieżka, to jeśli , wyprowadza ( u , v ) jako i- tą krawędź ścieżki od s do t . W przeciwnym razie zwiększ x , zmniejsz j , ustaw u : = v i ponownie uruchom pętlę for, jeśli v ≠ t .$x=i$$(u,v)$$i$$s$$t$$x$$j$$u := v$$v \neq t$

Jeśli po osiągnięciu t wyprowadza złe i (podane i było za duże).$x < i$$t$$i$$i$

Biorąc pod uwagę , ten algorytm albo wysyła i- tą krawędź na najkrótszej leksykograficznie ścieżce P od s do t , albo odrzuca.$i$$i$$P$$s$$t$