Konversi DNF ke CNF: Mudah atau Keras

Sehubungan dengan utas Membuktikan bahwa konversi dari CNF ke DNF adalah NP-Hard (dan utas Matematika terkait ):

Bagaimana dengan arah lain, dari DNF ke CNF? Apakah itu mudah atau sulit?

Pada halaman 2 makalah ini , mereka tampaknya mengisyaratkan bahwa kedua arah sama-sama sulit ketika mereka mengatakan " Kami tertarik pada ledakan maksimal ukuran ketika beralih dari representasi CNF ke representasi DNF (atau sebaliknya) ".

Tapi DNF-SAT dalam P dan CNF-SAT adalah NP -complete. Jadi dengan memberikan ekspresi DNF , harus ada ekspresi CNF yang setara yang memuaskan yang panjangnya polinomial dengan panjang . Dan konversi dapat dilakukan dalam waktu poli. Apakah ini benar? $\phi_1$ $\phi_2$ $\phi_1$ $\phi_1 \to \phi_2$

Sunting: Diubah setara dengan equisatisfiable (yaitu, variabel tambahan diizinkan di ). $\phi_2$

complexity-theory logic satisfiability normal-forms Martin Seymour
sumber

Anda dapat beralih dari formula apa saja ke CNF yang memuaskan persis ketika formula asli berada dalam waktu polinomial. Inilah sebabnya mengapa CNF-SAT adalah NP-lengkap. Setiap instance SAT (masalah NP-complete) dapat dikurangi menjadi CNF-SAT dalam waktu polinomial. Saya pikir persis menerjemahkannya, tidak hanya menjaga kepuasan akan selalu menghasilkan ledakan eksponensial tetapi saya tidak bisa mengatakan ini dengan pasti.

Jake

Lihat en.wikipedia.org/wiki/Tseitin_transformation . Pada dasarnya, jika Anda mengizinkan pengenalan variabel tambahan, Anda dapat melakukan transformasi ini dalam waktu-poli (meningkatkan ukuran rumus paling banyak secara linear).

jschnei

Anda harus memutuskan apakah Anda ingin mengizinkan konversi untuk memperkenalkan variabel baru atau apakah rumus yang dikonversi harus merujuk ke set variabel yang sama (tidak ada variabel baru). Ini adalah titik halus yang memiliki efek dramatis pada jawabannya. Jadi, yang ingin Anda tanyakan?

@Jake Anda dapat beralih dari formula apa saja ke CNF yang setara karena CNF-SAT adalah NP-complete. Itu sebenarnya bukan "mengapa" CNF-SAT adalah NP-complete: bukti biasa bahwa CNF-SAT adalah NP-complete tidak melibatkan penerjemahan rumus acak ke CNF; melainkan menerjemahkan mesin Turing ke dalam formula CNF.

David Richerby

Bagi DW dan yang lainnya - saya memiliki kepekaan yang sama dalam pikiran .. Dalam pengertian ini, tampaknya bahwa kepuasan hanya merupakan pengurangan (dalam hal ini, ke formula Boolean lain).

Martin Seymour

Jawaban:

Jika Anda ingin memperkenalkan variabel tambahan, Anda bisa mengonversi dari bentuk DNF ke CNF dalam waktu polinomial menggunakan transformasi Tseitin . Rumus CNF yang dihasilkan akan sesuai dengan rumus DNF asli: rumus CNF akan memuaskan jika dan hanya jika rumus DNF asli memuaskan. Lihat juga https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF .

Jika Anda tidak ingin mengizinkan pengenalan variabel tambahan, mengkonversi dari bentuk DNF ke CNF adalah co-NP-hard. Khususnya, menguji apakah formula DNF adalah tautologi adalah co-NP-hard. Namun, menguji apakah rumus CNF adalah tautologi dapat dilakukan dalam waktu polinomial (Anda hanya memeriksa secara terpisah apakah setiap klausa adalah tautologi, yang mudah karena setiap klausa merupakan disjungsi dari literal). Oleh karena itu, jika Anda dapat mengonversi dari formulir DNF ke formulir CNF dalam waktu polinomial, tanpa memperkenalkan variabel baru, maka Anda akan mendapatkan algoritme waktu polinomial untuk menguji apakah rumus DNF adalah tautologi - sesuatu yang tampaknya tidak mungkin, mengingat kami berharap P tidak sama dengan co-NP. Atau, dengan kata lain, mengubah dari bentuk DNF ke CNF tanpa memperkenalkan variabel tambahan adalah co-NP-hard.

Ini adalah perbedaan antara ekuivalensi vs kepuasan . Kesetaraan membutuhkan dua formula untuk memiliki rangkaian solusi yang sama (dan dengan demikian tidak memungkinkan memperkenalkan variabel tambahan). Kesamaan kepuasan hanya mensyaratkan bahwa kedua formula itu memuaskan atau keduanya tidak memuaskan (dan dengan demikian memungkinkan memperkenalkan variabel tambahan).

DW
sumber

@Mehrdad, tolong jangan gunakan komentar untuk mengajukan pertanyaan baru. Kami memiliki 'Ajukan Pertanyaan' di kanan atas karena jika Anda memiliki pertanyaan baru yang ingin Anda tanyakan. Tapi, hanya sedikit tip ... Anda mungkin ingin membaca pertanyaan di bagian atas halaman ini sebelum mengajukan pertanyaan baru ... atau, dalam hal ini, memposting komentar ini. Saya tidak bisa tidak memperhatikan bahwa Anda telah mengajukan pertanyaan di mana jawabannya ditemukan pada halaman yang sama dengan pertanyaan Anda.

@DW: Ups, saya benar-benar melihat posting lain sedikit sesudahnya dan lupa untuk menghapus komentar saya di sini, maaf. Dihapus sekarang.

user541686