Apakah semua kelas kompleksitas memiliki karakterisasi bahasa daun?

Bahasa daun adalah cara yang indah untuk secara seragam mendefinisikan banyak kelas kompleksitas. Sebagian besar kelas kompleksitas biasanya ditentukan oleh model perhitungan (misalnya, deterministik / acak TM), dan sumber daya terikat (waktu log, ruang poli, dll.). Namun dalam formulasi bahasa daun, hanya ada satu model perhitungan, dan kelas ditentukan dengan memberikan bahasa daunnya.

Detailnya terlalu panjang untuk dijelaskan, jadi saya akan mengarahkan pembaca yang tertarik ke salah satu dari dua survei ini:

1. Karakterisasi seragam dari kelas kompleksitas oleh H Vollmer
2. Leaf Language Classes oleh KW Wagner

Kedua survei melakukan pekerjaan yang baik untuk menjelaskan formulasi dalam beberapa halaman pertama.

Dalam survei Wagner, ia mengatakan "ternyata hampir setiap kelas kompleksitas yang dipertimbangkan sejauh ini dapat dijelaskan oleh bahasa daun."

Pertanyaan saya terkait dengan pernyataan ini. Saya tahu ada beberapa kelas yang kita tidak tahu karakter bahasa daun, jadi ini berarti baik kelas tidak memiliki karakterisasi seperti itu, atau kita belum menemukannya.

Apakah kita mengharapkan setiap kelas kompleksitas (katakanlah antara P dan PSPACE) memiliki karakterisasi bahasa daun? (Mari kita batasi diri kita pada kelas kompleksitas "alami"). Apakah ada hasil semacam ini dalam literatur?

(Sebuah pertanyaan terkait yang saya akan senang mengetahui jawabannya: Apakah ada metode (heuristik) untuk menghasilkan bahasa daun untuk kelas tertentu?)

EDIT: Suresh menunjukkan bahwa ada definisi pendek bahasa daun di artikel Wikipedia. Saya menyalinnya di bawah.

Beberapa kelas kompleksitas biasanya didefinisikan dalam istilah mesin Turing nondeterministic polinomial-waktu, di mana setiap cabang dapat menerima atau menolak, dan seluruh mesin menerima atau menolak sebagai beberapa fungsi dari kondisi cabang. Misalnya, mesin Turing non-deterministik menerima jika setidaknya satu cabang menerima, dan menolak hanya jika semua cabang menolak. Mesin Turing co-non-deterministik, di sisi lain, hanya menerima jika semua cabang menerima, dan menolak jika ada cabang yang menolak. Banyak kelas dapat didefinisikan dengan cara ini.

Lihatlah

Bernd Borchert, Riccardo Silvestri: Karakterisasi Kelas Bahasa Daun. Inf. Proses. Lett. 63 (3): 153-158 (1997) ( tautan doi di sini )

Para penulis mencirikan kelas bahasa daun sebagai kelas yang (a) "dapat dihitung", (b) "turun" ke arah polytec tertutup dan banyak yang dapat direduksi, dan (c) "gabungan-tutupan" (yaitu, disjoint union) wrt polytime banyak-satu reducibilitas.

$L$$C,D \in L$$E \leq^P_m C \sqcup D$$E \in L$$\sqcup$

$P/poly$$SPACE[n]$$SPACE[n] \neq P$$SPACE[n]$tidak ditutup di bawah pengurangan tersebut.)