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.
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.
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?
sumber