Membuktikan bahwa konversi dari CNF ke DNF adalah NP-Hard

20

Bagaimana saya dapat membuktikan bahwa konversi dari CNF ke DNF adalah NP-Hard?

Saya tidak meminta jawaban, hanya beberapa saran tentang bagaimana cara membuktikannya.

complexity-theory np-hard satisfiability sat-solvers normal-forms jkjk
sumber
5
Untuk analisis mendalam, lihat makalah ini "On Converting CNF to DNF"
Vor
@ A.Schulz: definisi asli dalam makalah Steve Cook mendefinisikannya menggunakan pengurangan Cook. Tampaknya itulah pengurangan yang digunakan ketika membahas kekerasan-NP umum en.wikipedia.org/wiki/NP-hard
Kaveh
CNF <-> Konversi DNF bukan keputusan, diperlukan untuk menjadi bahasa. ini lebih merupakan fungsi dengan input & output & itu harus dikonversi menjadi masalah keputusan untuk bertanya apakah dalam NP dll. berpikir bahwa masalah non keputusan telah terbukti mengarah pada ledakan eksponensial dalam ukuran [misalnya dalam Vors ref] karena itu sebuah Versi lengkap masalah keputusan NP [jika ada di luar sana] mungkin merupakan penyederhanaan yang signifikan. juga karena Vors ref menunjukkan kompleksitas aktual konversi CNF <-> DNF adalah masalah penelitian aktif ... perhatikan ada beberapa kesamaan dengan efisiensi algoritma kompresi ...
vzn
2
@ vzn Pertanyaannya menanyakan apakah NP-keras , bukan NP- lengkap. Ini berarti bahwa keanggotaan NP tidak diperlukan sehingga tidak harus menjadi masalah keputusan.
David Richerby

Jawaban:

18

Secara informal:

Di DNF, Anda dapat memilih klausa mana pun untuk menjadi kenyataan, untuk membuat formula itu benar. Ini berarti bahwa DNF yang setara dengan CNF tertentu, pada dasarnya adalah enumerasi semua solusi untuk boolean yang tersimpan di CNF. Catatan, mungkin ada sejumlah solusi eksponensial. Karena menyelesaikan boolean sat untuk CNF untuk satu solusi adalah NP-complete, konversi ke DNF pada dasarnya berarti pemecahan untuk setiap solusi. Jadi setidaknya sekeras Boolean SAT, dan karenanya NP-keras.

Realz Slaw
sumber