Untuk k manakah PLANAR NAE k-SAT dalam P?

23

Masalah Tidak Semua Sama dengan -SAT (NAE k -SAT), diberikan satu set C klausa atas seperangkat X variabel boolean sehingga setiap klausa berisi paling banyak k literal, menanyakan apakah ada penugasan kebenaran dari variabel sedemikian rupa sehingga setiap klausa berisi setidaknya satu true dan literal false.kkCXk

Masalah PLANAR NAE -SAT adalah pembatasan NAE k -SAT untuk kejadian-kejadian di mana kejadian grafik bipartit dari C dan X (yaitu grafik bagian C dan X dengan tepi antara x X dan c C jika dan hanya jika x atau ¯ x milik c ), adalah planar.kkCXCXxXcCxx¯c

Diketahui bahwa NAE 3-SAT adalah NP-lengkap (Garey dan Johnson, Komputer dan Intractability; Panduan untuk Teori NP-Completeness), tetapi PLANAR NAE 3-SAT ada di P (lihat Planar NAE3SAT di P, B Moret, ACM SIGACT News, Volume 19 Edisi 2, Musim Panas 1988 - sayangnya saya tidak memiliki akses ke makalah ini).

Apakah PLANAR NAE -SAT dalam P untuk beberapa k 4 ? Apakah ada nilai k yang telah ditunjukkan sebagai NP-complete?kk4k

Florent Foucaud
sumber

Jawaban:

23

PLANAR NAE -SAT dalam P untuk semua nilai k .kk

Alasannya adalah bahwa kita dapat mengurangi PLANAR NAE -SAT menjadi PLANAR NAE 3 -SAT. Biarkan ϕ menjadi turunan dari PLANAR NAE k -SAT, dan anggap ϕ berisi klausa C dengan literal 1 , 2 , , k . Perkenalkan variabel baru v C , dan ganti C dengan dua klausa NAE C 1 dan C 2 . C 1 berisi 3 literal 1 , 2k3ϕkϕC1,2,,kvCCC1C2C1312, dan , sedangkan C 2 berisi k - 1 literal ˉ v C , 3 , 4 , , k . Sangat mudah untuk melihat bahwa C adalah satisfiable IFF C 1C 2 dan bahwa transformasi menjaga planarity. Sekarang, kita dapat berulang kali menerapkan prosedur ini pada klausa untuk akhirnya mendapatkan instance ϕ dari NAE 3 -SAT seperti yang diinginkan.vCC2k1v¯C,3,4,,kCC1C2ϕ3

arnab
sumber
1
Jawaban yang bagus Apakah ini sudah diketahui?
Serge Gaspers
1
Kedengarannya seperti pengurangan ini "bekerja" bahkan tanpa syarat planar, jadi mungkin "diketahui"
Suresh Venkat
@Jadi, saya yakin itu, tapi saya tidak tahu referensi.
arnab
6
Ini adalah pengurangan standar, yang juga berfungsi untuk SAT "reguler". Anda dapat menemukannya misalnya dalam buku Sipser "Pengantar Teori Komputasi" dan banyak lagi.
5501