Konversi antara k-SAT dan XOR-SAT

Menurut XOR Satisfiability Solver Module untuk Integrasi DPLL oleh Tero Laitinen, kita membutuhkan klausa CNF untuk mengubah klausa XOR-SAT literal jika kita tidak ingin menambah jumlah literal. Jadi, saya mengerti bahwa biaya komputasi untuk mengubah ekspresi XOR-SAT menjadi CNF -SAT adalah eksponensial. n $2^{n-1}$$n$$k$

Pertanyaan saya: Berapa biaya komputasi jika saya ingin membalik prosesnya? Berapa biaya komputasi untuk mengubah ekspresi CNF -SAT menjadi ekspresi XOR-SAT? Saya berasumsi bahwa dalam kasus ini hanya ekspresi -SAT dengan ekspresi XOR-SAT yang setara yang dipertimbangkan.$k$$k$

Jika semua hubungan XOR antara variabel dalam rumus CNF dapat dideteksi dalam waktu polinomial, maka ini akan memungkinkan solusi UNAMBIGUOUS-SAT dalam waktu polinomial. Oleh teorema Valiant – Vazirani hasil ini akan menyiratkan bahwa NP = RP.

Untuk mengatasi ambigu-SAT, ingat bahwa menyiratkan sebuah ≠ b . Temukan hubungan XOR antara setiap pasangan variabel dan gunakan hasilnya untuk membagi variabel menjadi dua kelompok variabel yang setara. Setelah ini dilakukan, hanya dua tugas tes yang diperlukan untuk menentukan kepuasan.$a \oplus b$$a \neq b$

Dalam kasus terbatas memulihkan hubungan XOR yang dikodekan dengan cara biasa, yaitu

$a \oplus b \oplus c$

untuk

$\lnot a \lor b \lor c \\ a \lor \lnot b \lor c \\ a \lor b \lor \lnot c \\ \lnot a \lor \lnot b \lor \lnot c$

ini dapat dilakukan dalam waktu polinomial dengan menyortir klausa diikuti oleh pemindaian linear-waktu.