Rumus 3CNF Monoton terbatas: menghitung tugas yang memuaskan (baik modulo dan modulo )

Pertimbangkan formula Monotone 3CNF yang memiliki batasan tambahan berikut:

• Setiap variabel muncul tepat klausa.$2$
• Dengan klausa, mereka membagikan paling banyak 1 variabel.$2$$1$

Saya ingin tahu betapa sulitnya menghitung tugas yang memuaskan dari formula seperti itu.

Perbarui 06/04/2013 12:55

Saya juga ingin tahu seberapa sulit menentukan paritas dari jumlah tugas yang memuaskan.

Pembaruan 11/04/2013 22:40

Bagaimana jika, selain pembatasan yang dijelaskan di atas, kami juga memperkenalkan kedua batasan berikut:

• Rumusnya adalah planar.
• Rumusnya adalah bipartit.

Pembaruan 16/04/2013 23:00

Setiap tugas yang memuaskan sesuai dengan penutup tepi dari grafik reguler. Setelah pencarian yang ekstensif, satu-satunya makalah yang relevan yang dapat saya temukan pada penghitungan sampul tepi adalah (ke-3) yang telah disebutkan dalam jawaban Yuval. Pada awal makalah tersebut, penulis mengatakan "Kami memulai studi pengambilan sampel (dan pertanyaan terkait penghitungan) dari semua sampul tepi grafik" . Saya sangat terkejut bahwa masalah ini telah menerima begitu sedikit perhatian (dibandingkan dengan menghitung selimut titik, yang dipelajari secara luas dan jauh lebih dipahami, untuk beberapa kelas grafik). Kita tidak tahu apakah menghitung penutup tepi adalah . Kita tidak tahu apakah menentukan paritas jumlah penutup tepi adalah$3$$\#P$$\oplus P$-juga, baik.

Perbarui 09/06/2013 07:38

Menentukan paritas jumlah penutup tepi adalah , periksa jawaban di bawah ini.$\oplus P$

Dalam grafik apa pun, paritas jumlah penutup vertex sama dengan paritas jumlah penutup tepi.

Untuk mengetahui alasannya, periksa jawaban ini dan amati bagaimana paritassama dengan paritas , yang pada gilirannya sama dengan paritas , yang merupakan jumlah penutup tepi.Δ | V | = O | V | - E | V | O | V | + E | V $|C|$$\Delta_{|V|} = O_{|V|} - E_{|V|}$$O_{|V|} + E_{|V|}$

Komputasi paritas dari jumlah penutup vertex adalah P-hard: oleh karena itu menghitung paritas dari jumlah penutup tepi adalah P-hard juga.$\oplus$$\oplus$

Setidaknya setengah dari pertanyaan telah diselesaikan.

Masalah Anda mungkin # P-selesai, meskipun saya belum dapat menemukannya dalam literatur.

Cara lain untuk menyatakan masalah Anda adalah "# 3-regular-edge-cover". Diberikan rumus, buat grafik di mana setiap klausa bersesuaian dengan simpul dan masing-masing variabel berkorespondensi dengan suatu sisi. Karena rumusnya adalah 3CNF, grafiknya adalah 3-reguler (atau memiliki derajat maksimum 3, tergantung pada definisi). Lebih jauh, grafiknya sederhana. Tugas yang memuaskan sama dengan penutup tepi.

Berikut adalah beberapa masalah terkait:

• # 1-Ex3MonoSat adalah # P-complete . Ini sama dengan masalah Anda, hanya solusi yang memuaskan harus memenuhi tepat satu variabel di setiap klausa.
• Menghitung jumlah penutup simpul dalam grafik planar 3-reguler adalah # P-complete .
• Ada FPRAS untuk penutup tepi biasa # 3 . Ini menunjukkan bahwa penulis percaya bahwa masalahnya sulit.