Definisi Planar 3-SAT

10

Apa definisi standar Planar 3-SAT? Saya telah melihat sejumlah definisi berbeda. Apa kertas asli yang mendefinisikannya dan membuktikannya sebagai NP-complete?

pengguna24175
sumber
2
Apa yang menurut Anda membingungkan tentang hasilnya?
Niel de Beaudrap
Saya melihat definisi yang berbeda, seperti yang dikatakan beberapa orang: Grafik bipartit antara klausa dan literal harus planar (saya tidak tahu apakah literal artinya hanya x_i atau keduanya x_i dan negasinya, maksud saya saya tidak tahu apa milik mereka grafik gadget persis di sini?). Beberapa lainnya mendefinisikan dua jenis untuk itu: hanya tepi bipartit antara klausa dan literal, atau ini ditambah (x_i, ~ x_i). Atau ada yang mengatakan, grafik di atas ditambah (x_i, x_ {i + 1})? Saya bahkan tidak dapat menemukan kertas asli yang diterbitkan di sana? Pada dasarnya saya tidak dapat menemukan referensi yang bagus dengan definisi yang sempurna untuknya?
user24175
4
Referensi aslinya adalah: D. Lichtenstein, "Rumus Planar dan penggunaannya" (1982) ; tetapi ada banyak variasi kecil yang masih lengkap dengan NP (bukti NPC kebanyakan mudah).
Marzio De Biasi
1
@ Marszio De Biasi Terima kasih banyak! Tetapi, berdasarkan paer ini, planar 3-SAT adalah kasus bahwa grafik bipartit antara klausa yang literal (hanya x_i bukan negasinya) adalah planar. Baik? Kita dapat dengan mudah menyimpulkan kasus yang kita sertakan juga negasi dari x_i hanya dengan menambahkan keunggulan di antara mereka, tanpa mengganggu planaritas, kan?
user24175
1
@tinLoaf: sebagaimana dikutip dalam kuliah yang sangat baik yang dihubungkan oleh David Eppstein dalam jawabannya, Anda dapat melihat Mark de Berg dan Amirali Khosravi, Partisi Ruang Biner Optimal di Pesawat; di mana terbukti bahwa monoton planar 3-SAT adalah NPC: variabel ditempatkan pada garis horizontal, semua klausa positif digambar di atas, semua klausa negatif digambar di bawah; dalam representasi itu, mudah untuk mengganti setiap variabel dengan dua literal bertumpuk (dan juga ditautkan), literal positif atas, literal negatif bawah, tanpa melanggar kondisi planaritas. xsaya+xsaya-xsaya
Marzio De Biasi

Jawaban:

12

Ada kompilasi bagus definisi terkait masalah kelayakan planar NP-lengkap terkait di http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf

Salah satunya, planar monoton 3-sat, memungkinkan Anda untuk membagi setiap terminal menjadi positif dan negatif, dengan terminal ditempatkan di sepanjang garis dengan bagian positif di satu sisi garis dan bagian negatif di sisi lain dari garis. Klausa hanya memiliki terminal positif atau hanya negatif dan ditempatkan pada sisi positif atau negatif dari garis masing-masing.

David Eppstein
sumber