Apa itu dikotomi? Apakah 2-SAT itu sendiri merupakan dikotomi SAT?

Baru-baru ini, saya membaca makalah tentang dikotomi . Saya tidak mengerti kondisi apa yang bisa disebut dikotomi ? Apa arti dari "sebuah pertanyaan baik di P atau di NP - lengkap "? (asumsikan P NP )$\neq$

Sebagai contoh, saya sudah tahu teorema dikotomi Schaefer, di mana dikotomi tentang "apakah kelas SAT dalam P " diberikan. Dalam teorema ini, dikotomi berisi enam kondisi, salah satunya adalah "2-SAT".

Jadi pertanyaan saya adalah, apakah "2-SAT" itu sendiri dapat disebut sebagai dikotomi atau dikotomi sepele , karena 2-SAT dalam P tetapi 3-SAT adalah NP - lengkap ? Dengan kata lain, saya bertanya-tanya bahwa "jika kelas khusus masalah NP - lengkap ada di P , maka kelas ini adalah dikotomi? Atau dikotomi sederhana?"

Teorema dikotomi (kasar) menyatakan bahwa dalam kelas masalah tertentu, setiap masalah bisa dalam P atau NP-hard. Misalnya, teorema dikotomi Schaefer menyangkut kelas masalah bentuk . Berikut adalah kumpulan dari hubungan Boolean, dan adalah masalah memutuskan satisfiability proposisi yang konjungsi hubungan dari . Ini paling baik dijelaskan dengan sebuah contoh. Masalah 2SAT adalah dengan terdiri dari tiga predikat berikut: $\mathrm{SAT}(S)$$S$$\mathrm{SAT}(S)$$S$$\mathrm{SAT}(S_2)$$S_2$

$$(x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y.$$ Artinya, setiap instance dari 2SAT adalah konjungsi dari klausa salah satu dari tiga bentuk ini, di mana Anda dapat mengganti variabel apa pun yang Anda inginkan untuk . Sebagai contoh lain, HORNSAT adalah mana adalah koleksi tak terhingga berikut: Teorema dikotomi Schaefer menyatakan bahwa untuk masing-masing terbatas$x,y$$\mathrm{SAT}(S_H)$$S_H$ $$\begin{gather*} x \mapsto x, \quad x \mapsto \lnot x, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y, \\ (x,y,z) \mapsto x \lor \lnot y \lor \lnot z, \quad (x,y,z) \mapsto \lnot x \lor \lnot y \lor \lnot z, \\ (x,y,z,w) \mapsto x \lor \lnot y \lor \lnot z \lor \lnot w, \quad (x,y,z,w) \mapsto \lnot x \lor \lnot y \lor \lnot z \lor \lnot w, \ldots \end{gather*}$$ $S$ , masalah adalah dalam P atau NP-complete (ini adalah dikotomi karena hanya ada dua kemungkinan). Misalnya, 2SAT dan -HORNSAT berada di P untuk setiap , sedangkan 3SAT adalah NP-complete. Ini mengejutkan karena jika kita percaya bahwa P NP maka teorema Ladner menunjukkan bahwa ada masalah antara - masalah yang tidak ada dalam P atau NP-lengkap. Teorema Schaefer menunjukkan bahwa masalah-masalah ini tidak bisa dalam bentuk .$\mathrm{SAT}(S)$$k$$k$$\neq$$\mathrm{SAT}(S)$

Teorema Schaefer yang lebih disempurnakan menyatakan bahwa adalah dalam co-NLOGTIME, L-complete, NL-complete, L-complete, P-complete atau NP-complete. Dalam beberapa tahun terakhir, generalisasi yang tak terhitung dari teorema Schaefer telah terbukti atau dugaan, termasuk hasil tentang penghitungan solusi dan perkiraan jumlah maksimum klausa yang memuaskan, serta hasil atas domain non-Boolean. Dugaan utama adalah dugaan dikotomi Feder-Vardi yang menyatakan bahwa teorema Schaefer berlaku untuk hubungan pada domain ukuran terbatas yang sewenang-wenang. Untuk status teorema asli Schaefer dalam kasus di mana tidak terbatas, lihat pertanyaan ini .$\mathrm{SAT}(S)$$\oplus$$S$

Kata "dikotomi" berasal dari dikotomia Yunani yang berarti terbagi, atau terbelah dua. Jadi, dikotomi adalah pernyataan dalam bentuk apa pun, "Semuanya adalah A atau B tetapi tidak keduanya." Contoh klasiknya adalah, "Anda bersama kami atau melawan kami." Dikotomi Schaeffer untuk Boolean CSP (yang ia sebut "Generalized Satisfiability") adalah contoh lain: untuk setiap rangkaian hubungan Boolean yang terbatas, masalah kepuasan yang terkait adalah apakah dalam P atau NP-complete (tetapi tidak keduanya, dengan asumsi bahwa P NP). Teorema Kuratowski juga merupakan dikotomi: setiap grafik adalah planar berisi atau sebagai minor (topologis).$\neq$$K_5$$K_{3,3}$

Perhatikan bahwa dikotomi bukanlah akhir dari cerita dan dimungkinkan untuk menghasilkan klasifikasi yang lebih rinci. Anda mungkin sepenuhnya bersama kami atau hanya sedikit melawan kami. Beberapa kasus polinomial-kali dari teorema Schaeffer lebih mudah daripada yang lain (Allender, Bauland, Immerman, Schnoor, Voller, "Kompleksitas Masalah Kepuasan: Menyempurnakan Teorema Schaeffer" . Jurnal Ilmu Komputer dan Sistem , 75: 245-254, 2009.)