Kompleksitas st-Konektivitas Unik

Saya ingin tahu apakah masalah berikut dapat dipecahkan dalam (nondeterministic logspace):$\mathsf{NL}$

Diberikan grafik terarah dengan dua simpul dibedakan dan , apakah ada jalur unik dari ke di ?s t s t $G$$s$$t$$s$$t$$G$

Saya merasa bahwa itu kemungkinan ada di karena kita dapat memutuskan apakah ada - --path dan jika tidak ada jalan seperti itu. Namun, menghitung jumlah jalur tersebut adalah -hard (Valiant, 1979). s t ♯ $\mathsf{NL}$$s$$t$$\mathsf{\sharp P}$

Jadi pertanyaan saya: Apakah Anda punya referensi tentang ini? Apakah sudah jelas bahwa itu ada di ? Atau itu tidak ada di ?N $\mathsf{NL}$$\mathsf{NL}$

Tampaknya masalah Anda ada di . Berikut ini adalah algoritma.$NL$

Pertama, secara nondeterministis menebak jalur dari ke . Jika Anda salah menebak, tolak . Sebut algoritma ini .t $s$$t$$A$

Pertimbangkan algoritma nondeterministic berikut , yang menentukan apakah setidaknya ada dua jalur. Diberikan grafik dan , untuk semua pasangan tepi yang berbeda , tebak jalur dari ke yang mencakup tetapi bukan , lalu tebak jalur dari ke yang mencakup tetapi tidak . Jika tebakannya benar, terima . Jika tidak ada penerimaan untuk semua pilihan dan , tolak . Catatan dapat diterapkan di ruang log nondeterministic.s , t e , f s t e f s t f e e f $B$$s,t$$e,f$$s$$t$$e$$f$$s$$t$$f$$e$$e$$f$$B$

Sekarang, himpunan adalah himpunan grafik - dengan setidaknya dua jalur dari ke . Karena , komplemen juga dalam , yaitu, kita dapat menentukan apakah dan memiliki kurang dari dua jalur, dalam ruang log nondeterministic.s t s t N L = c o N L B N L s $L(B)$$s$$t$$s$$t$$NL = coNL$$B$$NL$$s$$t$

Algoritma terakhir adalah: "Jalankan Jika menerima, maka jalankan pelengkap dan output jawabannya."A $A$$A$$B$

Saya tidak tahu referensi.

PEMBARUAN: Jika Anda benar-benar menginginkan referensi, lihat paragraf pertama Bagian 3 dari makalah ini . Tapi ini mungkin hanya satu dari banyak referensi yang mengutip konsekuensi ini. Akan lebih masuk akal untuk menyebut hasilnya "cerita rakyat" daripada mengutip makalah yang menyebutkannya.

UPDATE 2: Anggaplah Anda ingin menentukan apakah ada jalur sederhana yang unik. Dalam hal ini, algoritma tidak harus berubah: jika ada jalur sama sekali maka ada jalur sederhana. Saya percaya modifikasi berikut akan bekerja untuk algoritma .$A$$B$

Kami ingin menulis ulang algoritme sehingga menerima jika ada setidaknya dua jalur sederhana.$B$

Pertama-tama pertimbangkan algoritma waktu polinomial berikut untuk masalahnya. Temukan jalur terpendek dari ke . Untuk setiap tepi dalam , periksa apakah ada jalur - yang tidak melalui . Jika Anda menemukan jalan seperti itu maka terima . Jika Anda tidak pernah menemukan jalan lain, tolak . Karena paling pendek, ia tidak memiliki siklus, dan jika ada jalur lain yang tidak menggunakan tepi , maka ada jalur lain yang sederhana dan tidak menggunakan tepis t e P s t e P P $P$$s$$t$$e$$P$$s$$t$$e$$P$$P$$P$. (Algoritma ini digunakan untuk masalah "jalur terpendek kedua").

Kami akan mengimplementasikan algoritma ini dalam . Jika kami memiliki algoritme untuk menanyakan tepi dalam jalur tetap , kami dapat mengimplementasikan hal tersebut di dalam nondeterministic logspace: iterasi melalui semua tepi dalam , tebak - path dan periksa bahwa untuk setiap tepi yang dikunjungi sepanjang jalan , tidak satupun dari mereka yang sama dengan .N L e P e P s t $NL$$NL$$e$$P$$e$$P$$s$$t$$e$

Jadi yang kita butuhkan adalah "jalur oracle", sebuah algoritma dengan properti: diberikan , dalam setiap jalur perhitungan algoritma baik melaporkan tepi ke- pada jalur - tetap tertentu , atau menolak . Kita bisa mendapatkan jalur oracle dengan menggunakan untuk mengisolasi jalur leksikografis pertama.i = 1 , … , n i s t N L = c o N $NL$$i=1,\ldots,n$$i$$s$$t$$NL=coNL$

Berikut ini adalah sketsa jalur oracle.

Temukan , panjang jalur terpendek dari ke , dengan mencoba semua dan menggunakan .s t k = 1 , … , n N L = c o N $k$$s$$t$$k=1,\ldots,n$$NL=coNL$

Setel variabel , , .x : = 1 j : = $u:=s$$x:=1$$j:=k$

Untuk semua tetangga dari agar leksikografis,$v$$u$

Tentukan apakah ada jalur dari ke dengan panjang (menggunakan hasil ). Lebih tepatnya, jalankan algoritma nondeterministic untuk konektivitas - (dengan panjang ) dan algoritma untuk komplemennya, secara bersamaan. Ketika salah satu dari mereka menerima, lanjutkan dengan jawabannya (itu pasti benar; keduanya tidak dapat menerima). Jika keduanya menolak maka tolak .t j - 1 N L = c o N L s t j - $v$$t$$j-1$$NL=coNL$$s$$t$$j-1$

Jika tidak ada jalan, lanjutkan ke tetangga berikutnya. Jika Anda sudah kehabisan semua tetangga maka tolak .

Jika ada jalur, maka jika , output sebagai tepi ke- di jalur dari ke . Jika tidak, tambahkan , turunkan , atur , dan mulai for-loop lagi jika .( u , v ) i s t x j u : = v v ≠ $x=i$$(u,v)$$i$$s$$t$$x$$j$$u := v$$v \neq t$

Jika setelah mencapai output bad (yang diberikan terlalu besar).t i$x < i$$t$$i$$i$

Diberikan , algoritma ini menghasilkan tepi ke- pada jalur pendek tersingkat secara leksikografis dari ke , atau menolak.i P s $i$$i$$P$$s$$t$