Model SAT unik vs Tepat

SAT unik adalah masalah yang terkenal: diberi rumus CNF , apakah benar memiliki satu model? $F$ $F$

Saya tertarik pada masalah «Persis -SAT»: diberikan rumus CNF dan integer , apakah benar memiliki model persis ? $m$ $F$ $m>1$ $F$ $m$

Kedua masalah terlihat serupa. Jadi pertanyaan saya adalah:

1- Apakah «Tepat -SAT» polytime (banyak orang atau Turing) dapat direduksi menjadi SAT Unik? $m$

2- Apakah Anda tahu referensi tentang masalah ini?

Terima kasih atas jawaban anda

Tambahan , artikel pertama tentang kerumitan Persis SAT: $m$

1- Janos Simon, Tentang Perbedaan Antara Satu dan Banyak, Dalam Prosiding Kolokium Keempat tentang Automata, Bahasa dan Pemrograman, 480-491, 1977.

2- Klaus W. Wagner, Kompleksitas masalah kombinatorial dengan representasi input ringkas, Acta Informatica, 23, 325-356, 1986.

Dalam kedua artikel, Persis SAT ( ) ditunjukkan menjadi lengkap (di bawah banyak-satu reduksi), di mana kelas berasal dari Menghitung Hirarki (CH) kelas kompleksitas. Secara informal, mengandung semua masalah yang dapat diekspresikan sebagai memutuskan apakah sebuah contoh yang diberikan memiliki paling sedikit banyak bukti ukuran polinomial (kelas diketahui bertepatan dengan kelas ). Kelas adalah varian , di mana "tepat " menggantikan "setidaknya ". $m$ $m \geq 1$ $C=$ $C$ $C$ $m$ $C$ $PP$ $C=$ $C$ $m$ $m$

cc.complexity-theory reference-request np-hardness sat reductions Xavier Labouze
sumber

Ini adalah polytime yang dapat direduksi oleh Turing: temukan solusi, tambahkan klausa untuk menghilangkannya, dan ulangi sampai formula menjadi tidak memuaskan.

Kaveh

1. mesin akan memberitahukan jumlah solusi atau bahwa ia memiliki lebih dari solusi

. 2. Anda dapat menambahkan negasi kata hubung yang menjelaskan solusi.

m

$m$

Kaveh

Jika Anda tidak tahu hubungan antara PP dan penghitungan jumlah solusi, silakan periksa buku teks tentang teori kompleksitas seperti Papadimitriou.

Tsuyoshi Ito

(1) Jika m dibatasi secara polinomi, masalah Anda adalah polinomial banyak waktu yang dapat direduksi menjadi SAT Unik dengan memperlakukan daftar solusi m yang diurutkan dalam urutan leksikografis sebagai satu sertifikat. (2) Tolong jangan menganggap jawaban saya sebagai bukti bahwa Anda mengajukan pertanyaan di tempat yang tepat. Saya pikir pertanyaan khusus ini ada di garis batas antara on-topic dan off-topic. Anda harus benar-benar mempertimbangkan untuk mengajukan pertanyaan masa depan Anda di tempat lain.

Tsuyoshi Ito

Meskipun Anda menyatakan bahwa m terikat secara polinomi, beberapa pernyataan dalam pertanyaan mengharuskan m untuk arbitrer dan tidak berlaku jika Anda membatasi m untuk dibatasi secara polinomi. Anda harus memahami apa yang Anda bicarakan sebelum Anda dapat mengajukan pertanyaan yang masuk akal. Inilah mengapa saya tidak ingin memposting jawaban untuk pertanyaan ini di sini, di mana pertanyaan diharapkan berada di tingkat penelitian.

Tsuyoshi Ito

Model SAT unik vs Tepat

Jawaban: