Kompleksitas penghitungan jalur dalam grafik

Diberikan grafik terarah dengan n simpul sehingga setiap simpul memiliki tepat dua tepi keluar, dan bilangan alami N yang dikodekan dalam biner, dua simpul s dan t,

Saya ingin menghitung jumlah jalur (tidak harus sederhana) dari s ke t dalam N langkah.

Apakah ini masalah # P-hard? Atau secara umum, apa kompleksitas dari masalah ini?

cc.complexity-theory graph-theory counting-complexity maomao
sumber

Apakah Anda mencoba menjalankan matriks?

Yuval Filmus

ya, tapi kompleksitasnya masih belum diketahui sejauh yang saya bisa lihat.

maomao

Apakah perjalanan harus berakhir pada t atau hanya mengunjungi t pada suatu titik dalam perjalanan?

Tyson Williams

itu harus berakhir pada t.

maomao

@Geekster Untuk digraf lengkap pada 3 simpul dengan , hitungannya adalah angka Fibonacci N, yang ukurannya eksponensial dalam N, sama seperti yang dikemukakan David dalam jawaban untuk grafik apa pun.

s \neq t

$s \ne t$

Tyson Williams

Jawaban:

Jumlah output jalur mungkin (pilih sewenang-wenang dan kemudian pilih sebagai titik yang merupakan titik akhir dari jumlah terbesar dari berjalan dari ) yang membutuhkan $\Omega(2^N/n)$ $s$ $t$ $2^N$ $s$ $\Omega(N)$ bit untuk ditulis secara eksplisit; ini eksponensial dalam ukuran input. Di sisi lain, pendekatan powering matriks memiliki kompleksitas polinomial dalam jumlah ukuran input dan output. Sehingga tampaknya menempatkannya tepat di kelas masalah penghitungan yang memiliki output berukuran eksponensial dan dapat diselesaikan secara polinomial waktu dalam ukuran output mereka, apa pun notasi untuk kelas itu (semacam penghitungan analog untuk EXP, dan pasti bukan #EXP yang lebih analog dengan NEXP).

David Eppstein
sumber

terima kasih, tapi saya masih ingin tahu apakah masalah ini -hard.

♯ P

$\sharp P$

maomao

Untuk menghindari jumlah besar dalam pendekatan iterated squaring David, kita dapat melakukan semua modulo perhitungan bilangan prima p. Kemudian algoritma keseluruhan berjalan dalam polinomial waktu di . Jika masalahnya adalah # P-hard di bawah banyak-satu pengurangan polinomial waktu, algoritma dengan akan menyiratkan P = P, yang kami tidak percaya.

n + \log N + \log p

$n + \log N + \log p$

p = 2

$p=2$

\oplus

$\oplus$

Holger

@ Holger tidak akan argumen serupa berlaku untuk Permanen? yaitu jika Permanen adalah # P-hard maka Perm mod 2 akan menjadi P hard. Tapi Perm mod 2 = Det mod 2 yang ada di P.

\oplus

$\oplus$

SamiD

@SamiD: Persis, argumen Anda menunjukkan bahwa permanen mungkin bukan # P-hard di bawah reduksi pelit . Bukti yang diketahui menggunakan reduksi Turing.

Holger

@ Holger saya setuju. Maaf saya telah melewatkan banyak-satu bagian yang pelit . Jadi masalah powering matriks powering mungkin # P-keras di bawah pengurangan Turing.

SamiD

Menemukan sedikit mana adalah adjacency matrix dari grafik yang diberikan berkurang ke masalah didefinisikan pertama dalam [ABKPM] yang memiliki batas bawah didirikan di kertas yang sama. Namun apakah pengurangan dalam arah sebaliknya berlaku, yaitu dari ke masalah powering matriks, adalah AFAIK terbuka. $A^N[s,t]$ $A$ $\mathsf{BitSLP}$ $\#\mathsf{P}$ $\mathsf{BitSLP}$

Perhatikan bahwa berada tepat di dalam hierarki penghitungan . Batas atas yang paling dikenal pada masalah ini yaitu. berasal dari sini . $\mathsf{BitSLP}$ $\mathsf{CH} \subseteq \mathsf{PSPACE}$ $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$

SamiD
sumber

Masalahnya adalah # P-selesai. Lihatlah masalah penghitungan jalur terpendek dalam grafik (ND31 di Garey & Johnson) yang merupakan # P-complete untuk versi penghitungan. Baca dengan seksama komentarnya. Hal ini memberikan jawaban untuk jalur panjang . Untuk mendapatkan jawaban untuk lintasan panjang , panggil masalah lintasan terpendek untuk dan , lalu kurangi yang terakhir dari yang sebelumnya, yaitu lakukan pengurangan subtraktif. $\leq N$ $=N$ $\leq N$ $\leq N-1$

Karena pengurangan dari #HAMILTONIAN PATHS / CIRCUITS ke #SHORTEST PATHS juga berfungsi untuk grafik 3-reguler, hasil # P-kelengkapan akan bekerja juga untuk pembatasan digraf Anda dengan derajat out-degree . $\leq 2$

Miki Hermann
sumber

Masalah aslinya tidak memerlukan jalan untuk menjadi sederhana, jadi saya tidak berpikir jawabannya benar.

maomao

Bagaimana itu bisa # P-selesai ketika semua masalah #P memiliki sejumlah solusi yang eksponensial dalam ukuran input dan yang satu ini eksponensial ganda?

David Eppstein

Apa arti "ND31" dalam konteks buku Garey dan Johson?

Tyson Williams