Tata bahasa konteks-sensitif untuk SAT?

16

Dengan hasil klasik Kuroda, kelas kompleksitas NSPACE [ ]n (juga dikenal sebagai NLIN-SPACE) adalah kelas CSL dari bahasa yang peka konteks . Masalah kepuasan SAT ada di NSPACE [ ], karena perkiraan ukuran linier untuk solusi dapat diperiksa dengan paling banyak jumlah linier overhead untuk pembukuan. Ini berarti bahwa SAT harus memiliki tata bahasa konteks-sensitif (CSG).n

Adakah yang mencoba memberikan CSG untuk SAT?

Saya menyadari banyak pertanyaan terkait dengan CSL tidak dapat diputuskan (misalnya memutuskan apakah CSG yang diberikan menghasilkan bahasa kosong). Bahkan diberi CSG untuk SAT orang masih harus mengatasi kendala bahwa memutuskan keanggotaan dalam bahasa yang diberikan oleh CSG adalah PSPACE-complete pada umumnya. Tetapi mungkin masalahnya bahwa masalah keanggotaan untuk CSG yang mendefinisikan SAT adalah dalam NP, karena beberapa struktur bahasa yang khusus. Mengulangi, untuk menanggapi komentar oleh KIA: Tetapi mungkin masalah keanggotaan CSG yang mendefinisikan SAT dapat ditunjukkan dalam NP karena beberapa struktur tata bahasa khusus, dan bukan karena kita sudah tahu itu harus dalam NP.


Klarifikasi:

Fokus yang dimaksudkan di sini adalah fitur khusus tata bahasa untuk SAT yang memungkinkannya untuk dikenali oleh mesin NTIME [poli ( )], daripada NSPACE [ ] DTIME [ ] terikat.nn2HAI(n)

Bukti Teorema 3 dalam makalah Landweber tahun 1963 membangun CSG dari otomat linear-bounded. (Kuroda memberikan yang sebaliknya, membuat otomat linear-terikat untuk CSG apa pun.) Namun, prosedur Landweber tampaknya tidak menghasilkan tata bahasa untuk SAT yang berbentuk khusus: semua pengenal NSPACE [ ] diperlakukan dengan cara umum yang sama. Dengan kata lain, tidak jelas mengapa SAT CSG harus memiliki masalah keanggotaan NP, daripada menyelesaikan PSPACE. Saya berharap untuk konstruksi yang lebih eksplisit yang menggunakan NP-ness SAT dalam beberapa cara yang penting.n

Mungkin pertanyaan yang lebih baik, lebih tepat, adalah apakah:

  1. ada otomat linear-terikat yang mengenali SAT,
  2. dari mana seseorang dapat mengekstrak CSG,
  3. sehingga bahasa yang didefinisikan oleh CSG adalah dalam NP karena beberapa fitur tata bahasa (dan bukan karena kita sudah tahu itu dalam NP)?

Dalam lima dekade terakhir, pasti seseorang telah mencoba melakukan ini! Karena saya tidak dapat menemukan apa pun yang diterbitkan di sepanjang baris ini, saya akan tertarik untuk memahami mengapa pendekatan ini tidak berhasil, atau petunjuk untuk bekerja yang saya lewatkan.

András Salamon
sumber
5
Saya tidak mengerti. Tidak bisakah Anda mengikuti buktinya dan menghasilkan CSG untuk SAT? Apakah ini tidak konstruktif? Juga tentang kalimat terakhir, "mungkin saja masalah keanggotaan CSG yang mendefinisikan SAT adalah NP", itu adalah NP karena masalah keanggotaan hanya SAT, yang ada di NP.
KIA
1
@MCH: Terima kasih atas komentar Anda, saya harap hasil edit menjelaskan pertanyaan.
András Salamon
kedengarannya seperti cara lain untuk ungkapan ini mungkin seperti ini: ada CSLs / CSGs yang dikenali dalam waktu NP (berbeda dengan PSPACE dalam kasus umum) berdasarkan konversi SAT. apa yang istimewa dari "struktur" mereka yang memungkinkan ini? mengkonversi SAT ke CSL / CSG mungkin memberikan "petunjuk" tetapi tidak nec. berikan kriteria yang lebih umum. dengan kata lain diberi CSL / CSG yang sewenang-wenang apakah ada beberapa kriteria yang menunjukkan pengakuannya sebenarnya dalam NP?
vzn

Jawaban:

9

Meskipun tidak secara langsung membangun tata bahasa yang peka konteks untuk SAT, makalah berikut mungkin menjelaskan.

Putaran WC, Kompleksitas pengakuan dalam bahasa tingkat menengah , Switching dan Automata Theory, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5

Makalah oleh Rounds memberikan otomat stack satu arah nondeterministik (1-NSA) mengenali SAT, dan kemudian menunjukkan masalah keanggotaan 1-NSA (dan superset yang tepat, Aho Indexed Grammar) secara umum dalam NP. Dengan kata lain, SAT sebagai CSL / linear-bound-automata adalah khusus dalam arti menggunakan memori hanya sebagai tumpukan.

kinaba
sumber
4
Terima kasih, persis apa yang saya cari! Rounds menunjukkan bahwa SAT adalah bahasa tumpukan satu arah, bahasa yang diindeks, dan bahasa transduser pohon, memberikan tiga alasan teoretis-bahasa yang berbeda mengapa itu istimewa.
András Salamon
jadi mungkin "cukup" tetapi tidak segera jelas apakah kondisi tersebut diperlukan (untuk pengakuan CSL / CSG dalam NP). jadi menurut saya sepertinya pertanyaan umum Anda mungkin tidak banyak dipelajari. CSL / CSG tampaknya tidak memiliki banyak riset di belakang mereka.
vzn
pemikiran lebih lanjut tentang ini. Masalahnya umumnya dalam bentuk "adalah pengenalan bahasa di kelas Y yang lebih besar sebenarnya di kelas bahasa X yang lebih kecil". untuk Y = CFG dan X = RL (bahasa biasa) masalahnya tidak dapat dipastikan lihat misalnya apakah cfg ini mendefinisikan bahasa biasa . oleh karena itu Y = CSL dan X = NP tampaknya juga tidak dapat diputuskan secara umum.
vzn