Bahasa Kelengkapan dan Konteks-Sensitif.

16

Saya tertarik pada dua pertanyaan tentang bahasa konteks-sensitif (CSL) dan kelengkapan:

  1. Apakah ada gagasan tentang kelengkapan untuk CSL, dan bahasa apa yang lengkap?
  2. Apakah ada CSL alami yang lengkap dengan NP?

Untuk 2., saya pasti bisa memikirkan bahasa NP-lengkap alami yang CSL (karena CSL sama dengan NSPACE [ ], SAT adalah CSL), tapi saya sedang mencari cara lain, yaitu, konteks- tata bahasa sensitif yang menggambarkan bahasa NP-lengkap.n

np-hardness fl.formal-languages space-bounded Michaël Cadilhac
sumber
2
Mari kita lihat apakah saya mengerti (2) dengan benar: Apakah cukup untuk menulis tata bahasa konteks-sensitif yang menghasilkan semua instance 3SAT yang valid atas alfabet tetap dari konektif dan variabel SAT?
Evgenij Thorstensen
1
Yah, saya tidak akan menambahkan variabel SAT sebagai bagian dari alfabet (pengkodean biner dari indeks mereka cukup baik), tapi itu pasti akan menjawab poin kedua saya!
Michaël Cadilhac
Omong-omong, apakah Anda mencobanya?
Michaël Cadilhac
4
(1) Seperti yang Anda sebutkan, dimungkinkan untuk menuliskan CSG untuk 3SAT, tetapi kedengarannya mirip dengan menuliskan deskripsi lengkap mesin Turing untuk masalah aliran maksimum (atau bahasa spesifik apa pun dalam P); Saya tidak berharap itu akan memberikan wawasan tentang teori kompleksitas. (Tapi hei, jika ternyata sebaliknya, saya akan senang mendengarnya.) (2) Secara umum, gagasan tata bahasa yang peka konteks dan gagasan tentang kelengkapan NP tidak berjalan bersama karena rangkaian peka konteks bahasa tidak ditutup di bawah pengurangan waktu polinomial.
Tsuyoshi Ito
1
Terima kasih atas komentarnya Tsuyoshi. Memang, tata bahasa untuk 3SAT mungkin bukan yang saya cari, tapi saya pergi dengan reaksi yang sama dengan Anda: jika itu agak mudah / alami, saya akan tertarik. Untuk (2) Anda, salah satu tujuan saya adalah sebagai berikut: katakanlah saya memiliki kelas bahasa CS yang ditutup oleh pengurangan spasi, dan saya ingin menunjukkan bahwa kelas saya tidak (atau tidak mungkin) mengandung masalah NP-complete, Saya hanya perlu menunjukkan bahwa bahasa CS NP-complete spesifik tidak di kelas saya, yang bisa lebih mudah jika bahasa tersebut secara alami CS.
Michaël Cadilhac

Jawaban:

9

Untuk menjawab pertanyaan pertama Anda, reducibilitas yang sesuai dengan kebutuhan Anda adalah reducibilitas log-lin-reducibility, yang merupakan reducibilitas logspace dengan kendala tambahan bahwa ukuran string output dari pengurangan paling banyak linier dalam ukuran input. Jika saya ingat dengan benar, masalah keanggotaan untuk tata bahasa yang peka konteks (atau, jika Anda suka, automata terikat linear) adalah masalah kanonik lengkap CSL-wrt log-lin reducibilitas.

Di sisi terapan, masalah universalitas dari ekspresi reguler (biasa) atas alfabet biner, adalah CSL-complete wrt log-lin-reducibility. Gagasan dan hasil kelengkapan ditemukan dalam Albert R. Meyer dan Larry J. Stockmeyer (SWAT 1972) juga: Stockmeyer (tesis PhD, MIT 1974). Untuk latar belakang lebih lanjut dan hasil serupa di daerah itu, lihat juga survei terbaru oleh Holzer dan Kutrib (DLT 2010).

EDIT (2017/03/06): Mengenai pertanyaan kedua Anda, jawaban yang diterima untuk pertanyaan di bawah ini mengutip makalah oleh Rounds (1973), yang membuat otomat stack satu arah yang mengenali SAT. Sementara SAT tidak akan memenuhi syarat sebagai CSL "alami", mungkin layak untuk mencari literatur untuk contoh-contoh lain dari stack automata stack satu arah atau tata bahasa yang diindeks.

Tata bahasa konteks-sensitif untuk SAT?

Hermann Gruber
sumber
Terima kasih banyak, ini memang yang saya cari!
Michaël Cadilhac
Untuk hasil edit: Fantastis! Terima kasih telah kembali ke sana dan menyelesaikan jawaban ini, ini adalah semangat yang hebat!
Michaël Cadilhac