Todas as classes de complexidade têm uma caracterização de idioma de folha?

Linguagens de folha são uma maneira bonita de definir uniformemente muitas classes de complexidade. A maioria das classes de complexidade é geralmente especificada por um modelo de computação (por exemplo, TM determinística / aleatória) e um recurso vinculado (tempo de log, espaço poligonal etc.). No entanto, na formulação da linguagem foliar, existe apenas um modelo de computação, e a classe é especificada fornecendo sua linguagem foliar.

Os detalhes são muito longos para serem explicados, por isso direcionarei os leitores interessados ​​para uma dessas duas pesquisas:

1. Caracterizações uniformes de classes de complexidade por H Vollmer
2. Aulas de idiomas por KW Wagner

Ambas as pesquisas explicam a formulação nas primeiras páginas.

Na pesquisa de Wagner, ele diz que "praticamente todas as classes de complexidade consideradas até agora podem ser descritas pelas linguagens foliares".

Minha pergunta está relacionada a esta afirmação. Eu sei que existem algumas classes para as quais não conhecemos uma caracterização da linguagem da folha, então isso significa que as classes não têm necessariamente essa caracterização ou não a encontramos.

Esperamos que toda classe de complexidade (digamos entre P e PSPACE) tenha uma caracterização de linguagem foliar? (Vamos nos restringir a classes de complexidade "naturais".) Existe algum resultado desse tipo na literatura?

(Uma pergunta relacionada à qual eu ficaria feliz em saber a resposta: Existe um método (heurístico) para criar uma linguagem de folha para uma determinada aula?)

EDIT: Suresh ressalta que há uma breve definição de idiomas das folhas no artigo da Wikipedia. Estou copiando abaixo.

Várias classes de complexidade são tipicamente definidas em termos de uma máquina de Turing não determinística em tempo polinomial, em que cada ramificação pode aceitar ou rejeitar, e a máquina inteira aceita ou rejeita como alguma função das condições das ramificações. Por exemplo, uma máquina de Turing não determinística aceita se pelo menos uma ramificação aceita e rejeita apenas se todas as ramificações rejeitarem. Uma máquina de Turing co-não-determinística, por outro lado, aceita apenas se todos os ramos aceitarem e rejeita se algum ramo rejeitar. Muitas classes podem ser definidas dessa maneira.

Dê uma olhada em

Bernd Borchert, Riccardo Silvestri: Uma Caracterização das Classes de Idiomas Foliares. Inf. Processo. Lett. 63 (3): 153-158 (1997) ( link aqui doi )

Os autores caracterizam as classes de idiomas das folhas como aquelas que são (a) "contáveis", (b) são polytime wrt fechadas para baixo e redutibilidade de muitas uma; redutibilidade de muitos.

$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]$não fechada sob essas reduções.)