Mengapa 2SAT dalam P?

Saya telah menemukan algoritma polinomial yang memecahkan 2SAT. Saya menemukan itu mengejutkan bahwa 2SAT ada di P di mana semua (atau banyak lainnya) dari instance SAT adalah NP-Complete. Apa yang membuat masalah ini berbeda? Apa yang membuatnya sangat mudah (Lengkap-NL - bahkan lebih mudah daripada P)?

Berikut adalah penjelasan intuitif dan bersahaja lebih lanjut di sepanjang baris jawaban MGwynne.

Dengan -SAT, Anda hanya dapat mengekspresikan implikasi dari bentuk , di mana dan adalah literal. Lebih tepatnya, setiap klausul dapat dipahami sebagai pasangan implikasi: dan . Jika Anda menetapkan true, harus benar juga. Jika Anda mengatur ke false, harus salah. Implikasi seperti itu sangat mudah: tidak ada pilihan, Anda hanya punya$2$$a \Rightarrow b$$a$$b$$2$$l_1 \lor l_2$$\lnot l_1 \Rightarrow l_2$$\lnot l_2 \Rightarrow l_1$$a$$b$$b$$a$$1$kemungkinan, tidak ada ruang untuk multiplikasi kasus. Anda bisa mengikuti setiap rantai implikasi yang mungkin, dan melihat apakah Anda pernah memperoleh keduanya dari dan dari : jika Anda melakukannya untuk beberapa , maka rumus 2-SAT tidak memuaskan, jika tidak memuaskan. Ini adalah kasus bahwa jumlah rantai implikasi yang mungkin secara polinomi dibatasi dalam ukuran formula input.$\lnot l$$l$$l$$\lnot l$$l$

Dengan -SAT, Anda dapat mengekspresikan implikasi dari bentuk , di mana , dan adalah literal. Sekarang Anda berada dalam kesulitan: jika Anda mengatur true, maka baik atau harus benar, tapi yang mana? Anda harus membuat pilihan: Anda memiliki 2 kemungkinan. Di sinilah multiplikasi kasus menjadi mungkin, dan di mana ledakan kombinatorial muncul.$3$$a \Rightarrow b \lor c$$a$$b$$c$$a$$b$$c$

Dengan kata lain, -SAT mampu mengekspresikan keberadaan lebih dari satu kemungkinan, sedangkan -SAT tidak memiliki kemampuan seperti itu. Justru adanya lebih dari satu kemungkinan ( kemungkinan dalam kasus -SAT, kemungkinan dalam kasus -SAT) yang menyebabkan ledakan kombinatorial tipikal dari masalah NP-complete.$3$$2$$2$$3$$k-1$$k$

Pertimbangkan resolusi pada formula 2-SAT. Setiap resolusi berukuran maksimal 2 (perhatikan bahwa jika untuk klausa panjang dan resp). Jumlah klausa ukuran 2 adalah kuadratik dalam jumlah variabel. Oleh karena itu, algoritma resolusi dalam P.$n + m -2 \le 2$$n, m \le 2$$n$$m$

Setelah Anda mendapatkan 3-SAT Anda bisa mendapatkan resolusi yang lebih besar dan lebih besar, jadi semuanya berjalan :) berbentuk pir.

Coba terjemahkan masalah ke dalam 2-SAT. Karena Anda tidak dapat memiliki klausa ukuran 3, Anda tidak dapat (secara umum) menyandikan implikasi yang melibatkan 3 variabel atau lebih, misalnya bahwa satu variabel adalah hasil dari operasi biner pada dua lainnya. Ini adalah batasan yang sangat besar.

Seperti kata Walter, klausa 2-SAT memiliki bentuk khusus. Ini dapat dimanfaatkan untuk mencari solusi dengan cepat.

Sebenarnya ada beberapa kelas instance SAT yang dapat diputuskan dalam waktu polinomial, dan 2-SAT hanyalah salah satu dari kelas yang dapat ditelusuri ini . Ada tiga macam alasan untuk keterlacakan:

1. (Penelusuran struktur) Setiap kelas dari instance SAT di mana variabel-variabel berinteraksi dengan cara yang mirip pohon dapat diselesaikan dalam waktu polinomial. Derajat polinomial tergantung pada lebar maksimum instance di kelas, di mana lebar mengukur seberapa jauh instance dari menjadi pohon. Lebih tepatnya, Marx menunjukkan bahwa jika instance telah membatasi lebar submodular, maka kelas dapat diputuskan dalam waktu polinomial menggunakan pendekatan divide-and-conquer.

2. (Keterlacakan bahasa) Setiap kelas dari instance SAT di mana pola variabel true-false adalah "bagus", dapat diselesaikan dalam waktu polinomial. Lebih tepatnya, pola literal mendefinisikan bahasa hubungan, dan Schaefer mengklasifikasikan enam bahasa yang mengarah pada kemampuan penelusuran, masing-masing dengan algoritma sendiri. 2-SAT membentuk salah satu dari enam kelas Schaefer.

3. (Penelusuran hibrid) Ada juga beberapa kelas instance yang tidak termasuk dalam dua kategori lainnya, tetapi dapat diselesaikan dalam waktu polinomial dengan alasan lain.

   • Dániel Marx, properti hypergraph yang dapat dilacak untuk kepuasan kendala dan pertanyaan konjungtif , STOC 2010. ( doi , pracetak )
   • Thomas J. Schaefer, Kompleksitas masalah kepuasan , STOC 1978. ( doi )

Jika Anda memahami algoritme untuk 2SAT, Anda sudah tahu mengapa itu ada di P - inilah yang ditunjukkan oleh algoritme. Saya pikir komik ini menggambarkan maksud saya. Seperti yang sudah Anda ketahui mengapa 2SAT ada di P, yang mungkin ingin Anda ketahui adalah mengapa 2SAT tidak NP-hard.

Untuk memahami mengapa 2SAT tidak NP-keras, Anda harus mempertimbangkan betapa mudahnya untuk mengurangi masalah lain di NP untuk itu. Untuk mendapatkan pemahaman intuitif tentang ini, lihat bagaimana SAT dapat dikurangi menjadi 3SAT dan cobalah menerapkan teknik yang sama untuk mengurangi SAT menjadi 2SAT. 2SAT tidak ekspresif seperti 3SAT dan varian SAT lainnya.