Apakah SAT bahasa bebas konteks?

Saya sedang mempertimbangkan bahasa dari semua formula logika proposisional yang memuaskan, SAT (untuk memastikan bahwa ini memiliki alfabet terbatas, kami akan menyandikan huruf proposisional dengan cara yang sesuai [edit: balasan menunjukkan bahwa jawaban untuk pertanyaan mungkin tidak kuat di bawah beragam pengkodean, jadi seseorang harus lebih spesifik - lihat kesimpulan saya di bawah ini] ). Pertanyaan sederhana saya adalah

Apakah SAT bahasa bebas konteks?

Dugaan pertama saya adalah bahwa jawaban hari ini (awal 2017) haruslah "Tidak ada yang tahu, karena ini berkaitan dengan pertanyaan yang belum terselesaikan dalam teori kompleksitas." Namun, ini tidak benar (lihat jawaban di bawah), meskipun tidak sepenuhnya salah juga. Berikut ini ringkasan singkat dari hal-hal yang kita ketahui (dimulai dengan beberapa hal yang jelas)

SAT tidak teratur (karena bahkan sintaksis logika proposisional tidak teratur, karena tanda kurung yang cocok)
SAT sensitif terhadap konteks (tidak sulit untuk memberikan LBA untuk itu)
SAT adalah NP-complete (Cook / Levin), dan khususnya diputuskan oleh TM non-deterministik dalam waktu polinomial.
SAT juga dapat dikenali oleh automata stack nondeterministic satu arah (1-NSA) (lihat WC Rounds, Kompleksitas pengakuan dalam bahasa tingkat menengah , Switching and Automata Theory, 1973, 145-158 http://dx.doi.org/ 10.1109 / SWAT.1973.5 )
Masalah kata untuk bahasa bebas konteks memiliki kelas kompleksitasnya sendiri $\textbf{CFL}$ (lihat https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cfl )
, di mana adalah kelas masalah logspace yang dapat direduksi menjadi (lihathttps://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#logcfl). Diketahui bahwa . $\textbf{CFL}\subseteq\textbf{LOGCFL}\subseteq\textbf{AC}^{\textbf{1}}$ $\textbf{LOGCFL}$ $\textbf{CFL}$ $\textbf{NL}\subseteq\textbf{LOGCFL}$
$\textbf{NL}\subsetneq\textbf{NP}$ $\textbf{NL}=\textbf{NP}$ $\textbf{NC}^{\textbf{1}}\subsetneq\textbf{PH}$ $\textbf{NP}$ $\textbf{LOGCFL}$ $\textbf{LOGCFL}$

Namun, poin terakhir ini masih menyisakan kemungkinan bahwa SAT diketahui tidak ada di . Secara umum, saya tidak dapat menemukan banyak tentang hubungan dengan hirarki yang mungkin membantu untuk memperjelas status epistemik pertanyaan saya. $\textbf{CFL}$ $\textbf{CFL}$ $\textbf{NC}$

Komentar (setelah melihat beberapa jawaban awal): Saya tidak mengharapkan rumus dalam bentuk normal konjungtif (ini tidak akan membuat perbedaan pada esensi jawaban, dan biasanya argumen masih berlaku karena CNF juga merupakan rumus. Tetapi klaim bahwa versi konstan dari jumlah variabel dari masalah adalah gagal biasa, karena kita membutuhkan tanda kurung untuk sintaks.).

Kesimpulan: Bertentangan dengan dugaan saya yang terinspirasi oleh teori kompleksitas, seseorang dapat menunjukkan secara langsung bahwa SAT tidak bebas konteks. Karena itu situasinya adalah:

Hal ini diketahui bahwa SAT adalah tidak bebas konteks (dengan kata lain: SAT tidak dalam ), dengan asumsi bahwa satu menggunakan "langsung" encoding formula di mana variabel proposisional diidentifikasi oleh bilangan biner (dan beberapa simbol lebih lanjut digunakan untuk operator dan pemisah). $\textbf{CFL}$
Tidak diketahui apakah SAT ada di , tetapi "sebagian besar pakar berpikir" itu tidak, karena ini akan menyiratkan . Ini juga berarti bahwa tidak diketahui apakah penyandian SAT "masuk akal" lainnya bebas konteks (dengan asumsi bahwa kami akan mempertimbangkan ruang log sebagai upaya penyandian yang dapat diterima untuk masalah NP-hard). $\textbf{LOGCFL}$ $\textbf{P}=\textbf{NP}$

Perhatikan bahwa kedua poin ini tidak menyiratkan . Ini dapat ditunjukkan secara langsung dengan menunjukkan bahwa ada bahasa dalam (maka dalam ) yang tidak bebas konteks (misalnya, ). $\textbf{CFL}\subsetneq\textbf{LOGCFL}$ $\textbf{L}$ $\textbf{LOGCFL}$ $a^nb^nc^n$

cc.complexity-theory circuit-complexity sat context-free mak
sumber

Jika ya, maka P = NP.

Ryan

Jika SAT bebas konteks maka pemrograman dinamis (algoritma CYK) akan memberikan algoritma waktu polinomial untuk menguji keanggotaan dalam SAT, memberikan P = NP. Bahkan P = NP tidak akan berarti SAT bebas dari konteks. Pengodean variabel ini sepertinya lebih penting daripada Anda memberinya kredit. Saya belum mengerjakan detailnya tetapi jika Anda menambahkan "subskrip" unary atau biner ke variabel, saya pikir Anda akan kesulitan membedakan (x dan y) dari (x dan bukan x) untuk indeks yang cukup besar.

AdamF

Anda harus tepat tentang representasi sebelum mengklaim kesimpulan P = NP. Misalnya, memfaktorkan angka N adalah waktu polinomial dalam N (pertanyaan menarik adalah mengenai jumlah bit yang diperlukan untuk menulis N dalam biner, atau tentang log N).

Aryeh

Saya menyadari P = NP kesimpulan dan karena itu jawabannya tidak diharapkan menjadi "ya" (maaf karena sedikit provokatif dalam cara saya mengutarakan ini ;-). Saya masih bertanya-tanya apakah ini benar-benar diketahui atau hanya sesuatu yang "sebagian besar ahli percaya" (jawaban sekarang jelas menunjukkan bahwa yang pertama benar; saya akan memilih satu nanti).

mak

Jawaban:

Hanya bukti alternatif menggunakan campuran hasil yang terkenal.

Seandainya:

variabel diekspresikan dengan ekspresi reguler $d = (+|-)1(0|1)^*$
dan bahasa ( reguler ) (lebih dari digunakan untuk mewakili rumus CNF adalah: ; perhatikan bahwa mengambil semua rumus CNF yang valid hingga penggantian nama variabel. $\Sigma = \{0,1,+,-,\land,\lor\})$ $S = \{ d^+ (\lor d^+)^*(\land (d^+ (\lor d^+)^*))^* \}$ $S$

Misalnya ditulis sebagai: ( operator memiliki prioritas lebih dari ) . $\varphi = (x_1 \lor x_2) \land -x_3$ $s_{\varphi} = +1 \lor +10 \land -11 \in S$ $\lor$ $\land$

Misalkan formula yang sesuai memuaskan adalah CF. $L = \{ s_{\varphi} \in S \, \mid$ $\varphi$ $\}$

Jika kita memotongnya dengan bahasa reguler: kita masih mendapatkan bahasa CF. Kita juga dapat menerapkan homomorfisme: , dan bahasanya tetap CF. $R = \{ +1^a \land -1^b \land -1^c \mid a,b,c > 0 \}$ $h(+) = \epsilon$ $h(-) = \epsilon$

Tetapi bahasa yang kita peroleh adalah: , karena jika maka rumus "sumber" adalah yang tidak memuaskan (sama jika ). Tapi adalah sebuah kontradiksi non-bahasa non CF yang terkenal . $L' = \{ 1^a \land 1^b \land 1^c \mid a \neq b, a \neq c\}$ $a=b$ $+x_a \land -x_a \land -x_b$ $a=c$ $L'$ $\Rightarrow$

Marzio De Biasi
sumber

Saya menerima jawaban ini sekarang karena masih ada masalah terbuka dengan pendekatan lain (lihat komentar) dan saya suka argumen yang agak lebih mendasar. Mungkin lebih baik untuk menekankan bahwa argumen itu spesifik untuk pengkodean yang dipilih dan memang tidak diketahui jika seseorang dapat menemukan pengkodean sederhana (logspace) yang mengarah ke bahasa bebas konteks.

mak

@mak: Saya menduga bahwa penyandian SAT "masuk akal" lainnya dapat dibuktikan non CF dengan teknik serupa. Mungkin arah lain yang menarik adalah untuk belajar jika kita dapat menerapkan semacam diagonalisasi untuk mendapatkan bukti yang lebih umum: rumus SAT mengkode perhitungan yang mensimulasikan push down automata pada input yang diberikan dan itu memuaskan jika dan hanya jika tidak t menerimanya. Tapi itu hanya gagasan kabur ...

Marzio De Biasi

Memeriksa apakah string dalam bahasa biasa adalah dalam P. Asumsikan SAT dalam Reg. Kemudian NP = coNP. Biarkan L berada di Reg. Pertimbangkan rumus yang benar jika tidak dalam L. Itu dalam NP sehingga dapat dinyatakan sebagai rumus SAT. Itu dalam bahasa jika tidak.

Kaveh

Jika jumlah variabel terbatas, maka jumlah konjungsi yang memuaskan, jadi bahasa SAT Anda terbatas (dan karenanya teratur). [Sunting: klaim ini mengasumsikan formulir CNFSAT.]

Kalau tidak, mari kita sepakat untuk menyandikan rumus seperti oleh . Kami akan menggunakan lemma Ogden untuk membuktikan bahwa bahasa semua konjungsi yang memuaskan tidak bebas konteks. $(x_{17}\vee \neg x_{21})\wedge (x_{1}\vee x_{2}\vee x_3)$ $(17+\tilde{} 21)(1+2+3)$

Misalkan adalah konstanta "penandaan" dalam lemma Ogden, dan pertimbangkan rumus sat dengan klausa pertama terdiri dari - yaitu, pengkodean , di mana adalah angka desimal yang terdiri dari yang Kami menandai yang dan kemudian mengharuskan semua pemompaan dekomposisi sesuai (lihat kesimpulan dari lemma Ogden) juga memuaskan. Tetapi kita dapat dengan mudah memblokir ini dengan mensyaratkan bahwa tidak ada klausa yang mengandung , di mana adalah urutan lebih pendek dari $p$ $w$ $(1^p)$ $(x_N)$ $N$ $p$ $p$ $1^p$ $w$ $x_q$ $q$ $1$ $p$ , menjadi memuaskan - misalnya, dengan memastikan bahwa setiap klausa lain dari memiliki negasi dari setiap . Ini berarti bahwa gagal properti "pemompaan negatif" dan kami menyimpulkan bahwa bahasa tersebut tidak bebas konteks. [Catatan: Saya telah mengabaikan kasus sepele di mana pemompaan menghasilkan string yang buruk.] $w$ $x_q$ $w$

Aryeh
sumber

Catatan: Dalam klaim saya bahwa untuk sejumlah variabel terbatas bahasa itu terbatas, saya secara implisit melarang pengulangan variabel dalam klausa atau klausa tanpa batas berkali-kali

Aryeh

... Tapi saya pikir bahasanya masih teratur, karena orang mengambil koleksi terbatas "dasarnya berbeda" (yaitu, tanpa pengulangan sepele) rumus dan kemudian memungkinkan berbagai pengulangan.

Aryeh

Klaim dengan keteraturan hanya berfungsi untuk CNFSAT (saya menambahkan klarifikasi ke pertanyaan saya).

mak

Bahkan dengan rumus non-CNF yang berubah-ubah dalam banyak variabel, kepuasan (dan bahasa apa pun yang tidak dapat membedakan dua rumus yang setara secara logis dalam hal ini) mudah dilihat bebas konteks. Namun, saya gagal melihat relevansinya. Kepuasan formula dalam banyak variabel secara halus adalah masalah sepele yang tidak ada hubungannya dengan kompleksitas SAT.

Emil Jeřábek 3.0

OK, saya melihat masalahnya - saya secara implisit mengasumsikan bahwadapat dibatasi panjangnya (seperti dalam lemma pemompaan klasik), sementara juga bisa menentukan sesuatu tentang lokasinya di string. Saya pikir argumen dapat diperbaiki dengan kembali melakukan pemompaan lemma dari awal. Kita akan membuat variabel pertama itu urutan yang sangat panjang dari 1's - cukup lama sehingga beberapa sub-pohon menghasilkan substring yang berdekatan dari 1 itu harus cukup dalam untuk diterapkan pada prinsip pidgeonhole.

| x y z |

$|xyz|$

Aryeh