Apa definisi standar Planar 3-SAT? Saya telah melihat sejumlah definisi berbeda. Apa kertas asli yang mendefinisikannya dan membuktikannya sebagai NP-complete?
cc.complexity-theory
reference-request
np-hardness
sat
planar-graphs
pengguna24175
sumber
sumber
Jawaban:
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.
sumber