Apakah 2-SAT dengan XOR-relations NP-complete?

11

Saya bertanya-tanya apakah ada algoritma polinomial untuk "2-SAT dengan hubungan XOR". Baik 2-SAT dan XOR-SAT berada di P, tetapi apakah kombinasinya?

Input Contoh:

  • Bagian 2-SAT: (a or !b) and (b or c) and (b or d)

  • Bagian XOR: (a xor b xor c xor 1) and (b xor c xor d)

Dengan kata lain, inputnya adalah rumus boolean berikut:

(a∨¬b)∧(b∨c)∧(b∨d)∧(a⊕b⊕¬c)∧(b⊕c⊕d).

Contoh Output: Memuaskan: a = 1, b = 1, c = 0, d = 0.

Baik jumlah klausa 2-SAT dan jumlah klausa XOR dalam input adalah , di mana adalah jumlah variabel boolean.nO(n)n

np-complete satisfiability xor 2-sat Albert Hendriks
sumber
1
masalah ini cukup dekat, bitor xor vektor untuk sama dengan vektor target , cstheory.se
vzn

Jawaban:

11

2-SAT-dengan-XOR-relasi dapat dibuktikan NP-lengkap dengan reduksi dari 3-SAT. Setiap klausa 3-SAT dapat ditulis ulang ke dalam ekspresi relasi 2-SAT-dengan-XOR yang setara dengan dan sebagai variabel baru.

(x1∨x2∨x3)
(x1∨y¯)∧(y⊕x2⊕z)∧(z¯∨x3)
yz
Kyle Jones
sumber
Semua jawaban tampaknya benar atau membantu, tetapi saya menemukan ini yang paling elegan (imho).
Albert Hendriks
1
Jawaban bagus. Mungkin perlu disebutkan bahwa kesetaraan semata tidak akan cukup di sini (karena penugasan yang memuaskan dari ekspresi yang sesuai dengan semua klausa dari CNF yang memuaskan mungkin tidak cocok), tetapi ekspresi yang ditulis ulang Anda sebenarnya memiliki penugasan yang memuaskan yang sesuai untuk setiap penugasan yang memuaskan dari klausa asli.
Klaus Draeger
7

Anda belum menentukan arity dari hubungan XOR Anda, tetapi seperti dalam pengurangan SAT-to-3SAT yang biasa, Anda selalu dapat mengatur bahwa arity mereka paling banyak 3. Sekarang Anda berada dalam posisi yang tepat untuk menerapkan teorema dikotomi Schaefer , yang akan memberi tahu Anda apakah masalah Anda ada di P atau NP-complete (ini adalah hanya dua opsi). Jika ternyata berada di P, langkah selanjutnya bisa melihat Allender et al. , yang akan memberi tahu Anda betapa mudahnya masalah Anda.

Yuval Filmus
sumber
Ini tidak memperhitungkan kondisi bahwa ada batasan , tetapi Anda selalu dapat menambahkan variabel dummy untuk memastikan bahwa kondisi terpenuhi. O(n)
Yuval Filmus
5

Menurut teorema dikotomi Schaefer , ini adalah NP-complete.

Pertimbangkan kasus di mana semua klausa memiliki 2 atau 3 literal di dalamnya; maka kita dapat menganggap ini sebagai masalah kepuasan kendala atas seperangkat hubungan arity 3. Secara khusus, hubungan adalah sebagai berikut: , , , , .R ( x , y , z ) x ∨ y x ∨ ¬ y ¬ x ∨ ¬ y x ⊕ y ⊕ z x ⊕ y ⊕ ¬ zΓR(x,y,z)x∨yx∨¬y¬x∨¬yx⊕y⊕zx⊕y⊕¬z

Sekarang terapkan teorema dikotomi Schaefer, dalam bentuknya yang modern . Periksa masing-masing dari enam operasi untuk melihat apakah mereka polimorfisme:

  • Unary 0: Bukan polimorfisme dari .x∨y
  • Unary 1: Bukan polimorfisme dari .¬x∨¬y
  • Biner DAN: Bukan polimorfisme . (Pertimbangkan dan ; mereka berdua memuaskan hubungannya, tetapi titik-AND mereka tidak.)x∨y(0,1,0)(1,0,0)(0,0,0)
  • Biner ATAU: Bukan polimorfisme dari . (Pertimbangkan dan ; mereka memenuhi hubungan, tetapi tidak.)¬x∨¬y(0,1,0)(1,0,0)(1,1,0)
  • Mayoritas ternary: Bukan polimorfisme . (Pertimbangkan dan dan ; mereka memenuhi hubungan, tetapi mayoritas mereka tidak.)x⊕y⊕z(0,0,1)(0,1,0)(1,0,0)(0,0,0)
  • Minoritas ternary: Bukan polimorfisme . (Pertimbangkan , , dan ; mereka memuaskan hubungannya, tetapi minoritas mereka tidak.)x∨y(0,1,0)(1,0,0)(1,1,0)(0,0,0)

Oleh karena itu masalah ini adalah NP-lengkap, bahkan jika Anda membatasi semua klausa XOR panjangnya paling banyak 3.

Di sisi lain, jika semua klausa XOR dibatasi paling panjang 2, maka ini dalam P. Secara khusus setara dengan , sehingga rumus seperti itu setara dengan rumus 2SAT, yang kepuasannya dapat ditentukan dalam waktu polinomial.( x ∨ y ) ∧ ( ¬ x ∨ ¬ y )(x⊕y)(x∨y)∧(¬x∨¬y)

DW
sumber