Kondisi planaritas untuk Planar 1-in-3 SAT

Planar 3SAT adalah NP-complete. Contoh planar 3SAT adalah instance 3SAT yang grafiknya dibuat menggunakan aturan berikut adalah planar:

1. tambahkan simpul untuk setiap dan ¯ x $x_i$$\bar{x_i}$
2. tambahkan simpul untuk setiap klausa $C_j$
3. menambahkan keunggulan untuk setiap pasangan$(x_i,\bar{x_i})$
4. tambahkan edge dari vertex (atau ¯ x i ) ke setiap vertex yang mewakili klausa yang berisi itu$x_i$$\bar{x_i}$
5. menambahkan tepi antara dua variabel berturut-turut $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

Secara khusus, aturan 5 membangun "tulang punggung" yang membagi klausa di dua wilayah yang berbeda.

Planar 1-in-3 SAT juga NP-complete.

Tetapi untuk planar 1-in-3 SAT, apakah kondisi planaritas didefinisikan dengan cara yang sama seperti pada Planar 3SAT? Secara khusus, dapat kita asumsikan bahwa ada tulang punggung yang link variabel ? $(x_i,x_{i+1})$

Ya kamu bisa. Sebenarnya Anda bahkan dapat menunjukkan bahwa sesuatu yang lebih kuat itu benar. Masalahnya tahu sebagai Planar Positif 1-in-3-SAT adalah NP-lengkap seperti yang ditunjukkan oleh Mulzer dan Rote .

Dalam versi 1-in-3-SAT ini, Anda perlu untuk setiap formula input itu

• Anda memiliki tiga variabel per klausa, tidak ada satupun yang dinegasikan
• grafik rumus adalah planar, bahkan jika Anda menambahkan "tulang punggung" antara simpul variabel

Pengurangannya dari Planar 3-SAT .