Ada algoritma polinomial yang mudah untuk memutuskan apakah ada jalur antara dua node dalam grafik terarah (cukup lakukan traversal grafik rutin dengan, katakanlah, pencarian-kedalaman-pertama).
Namun tampaknya, secara mengejutkan, masalahnya menjadi lebih sulit jika alih-alih menguji keberadaan kami ingin menghitung jumlah jalur.
Jika kita mengizinkan jalur untuk menggunakan kembali simpul maka ada solusi pemrograman dinamis untuk menemukan jumlah jalur dari s ke t dengan n tepi. Namun, jika kita hanya mengizinkan jalur sederhana, yang tidak menggunakan kembali simpul, satu-satunya solusi yang dapat saya pikirkan adalah enumerasi brute force dari jalur , sesuatu yang memiliki kompleksitas waktu eksponensial.
Jadi saya bertanya,
- Apakah menghitung jumlah jalur sederhana antara dua simpul itu sulit?
- Jika demikian, apakah ini semacam NP-complete? (Saya katakan semacam itu karena secara teknis bukan masalah keputusan ...)
- Apakah ada masalah lain di P yang memiliki versi penghitungan yang sulit seperti itu juga? **
Jawaban:
Kelas kompleksitas paling umum yang terkait dengan penghitungan masalah adalah #P . Memutuskan apakah ada jalur sederhana dari node yang diberikan ke yang lain jelas dalam NP. Menghitungnya kemudian di #P.
Tentang kelengkapan NP: bahkan jika itu bukan masalah keputusan, itu hampir tidak cocok di NP: mungkin adajalur, dan non-determinisme tidak membantu Anda tentang hal itu (Anda masih perlu memeriksa semuanya)n!
Jawaban atas dua pertanyaan pertama Anda adalah: ya, sulit, itu # P-complete (ref) .
Artikel Wikipedia memberikan fakta-fakta terkait: 1) algoritma probabilistik berguna untuk memperkirakan fungsi-fungsi # P-complete, dan itulah jenis algoritma yang digunakan untuk perkiraan pada artikel sebelumnya. 2) Ada masalah mudah lainnya dengan versi penghitungan yang sulit (# P-complete):
Anda sudah tahu bahwa jika Anda menghapus kendala "jalur sederhana" masalahnya jatuh ke P (yah Anda harus mengikat panjang jalur dengan polinomial ukuran grafik atau memberikan batas unary)
sumber