Apa yang diketahui tentang transisi fase dalam masalah # P-Complete? Secara khusus, apakah ada transisi fase yang berbeda untuk # DNF-k-SAT dan # CNF-k-SAT?
Pembaruan:
Seperti yang kita ketahui, ada fase transisi dalam Random k-SAT di mana penyelesaian masalah berubah dari yang mudah ke sulit dan kembali ke mudah lagi. Saya ingin tahu apakah ada fenomena seperti itu untuk masalah # P-Complete juga. Lebih penting lagi, jika ada transisi fase, apakah sama untuk # CNF-k-SAT dan # DNF-k-SAT?
Saya berpikir bahwa ada beberapa jenis transisi fase untuk # CNF-k-SAT. Di sisi lain, saya tidak berpikir ada transisi fase untuk # DNF-k-SAT dan masalahnya semakin sulit karena kami menambahkan lebih banyak klausa ....
11
Jawaban:
Untuk menghitung set independen, ada bukti terbaru untuk transisi fase komputasi, oleh Allan Sly: http://arxiv.org/abs/1005.5584 (algoritma ini oleh Dror Weitz dari 2006; Allan membuktikan kekerasan yang cocok dan menang bersama) penghargaan kertas terbaik di FOCS'10 untuk itu)
Perhatikan bahwa untuk 3SAT acak dan masalah serupa, tidak ada bukti bahwa masalah tersebut memang sulit pada interval yang sesuai. Ketika Anda pergi ke masalah penghitungan yang lebih sulit, menjadi lebih mudah untuk membuktikan kekerasannya.
sumber