¿Todas las clases de complejidad tienen una caracterización de lenguaje hoja?

Los lenguajes de hoja son una forma hermosa de definir uniformemente muchas clases de complejidad. La mayoría de las clases de complejidad generalmente se especifican mediante un modelo de cálculo (por ejemplo, TM determinista / aleatorizado) y un límite de recursos (tiempo de registro, espacio polivinílico, etc.). Sin embargo, en la formulación del lenguaje hoja, solo hay un modelo de cálculo, y la clase se especifica dando su lenguaje hoja.

Los detalles son demasiado largos para explicarlos, así que dirijo a los lectores interesados ​​a cualquiera de estas dos encuestas:

1. Caracterizaciones uniformes de clases de complejidad por H Vollmer
2. Clases de lenguaje de hoja por KW Wagner

Ambas encuestas hacen un gran trabajo al explicar la formulación en las primeras páginas.

En la encuesta de Wagner, dice que "resulta que prácticamente todas las clases de complejidad consideradas hasta ahora pueden ser descritas por lenguajes de hoja".

Mi pregunta se refiere a esta declaración. Sé que hay algunas clases para las que no conocemos una caracterización del lenguaje hoja, por lo que esto significa que las clases no necesariamente tienen tal caracterización o no la hemos encontrado.

¿Esperamos que cada clase de complejidad (digamos entre P y PSPACE) tenga una caracterización de lenguaje hoja? (Limitémonos a las clases de complejidad "natural".) ¿Hay algún resultado de este tipo en la literatura?

(Una pregunta relacionada a la que me encantaría saber la respuesta: ¿Existe un método (heurístico) para crear un lenguaje hoja para una clase determinada?)

EDITAR: Suresh señala que hay una breve definición de lenguajes de hoja en el artículo de Wikipedia. Lo estoy copiando a continuación.

Varias clases de complejidad se definen típicamente en términos de una máquina de Turing no determinista de tiempo polinomial, donde cada rama puede aceptar o rechazar, y toda la máquina acepta o rechaza como alguna función de las condiciones de las ramas. Por ejemplo, una máquina de Turing no determinista acepta si al menos una rama acepta, y rechaza solo si todas las ramas rechazan. Una máquina de Turing co-no determinista, por otro lado, acepta solo si todas las ramas aceptan, y rechaza si alguna rama rechaza. Muchas clases se pueden definir de esta manera.

Mira esto

Bernd Borchert, Riccardo Silvestri: una caracterización de las clases de lenguaje de hoja. Inf. Proceso. Letón. 63 (3): 153-158 (1997) ( enlace doi aquí )

Los autores caracterizan las clases de lenguaje de la hoja como aquellas que son (a) "contables", (b) son "descendentes" wrt polytime reducibilidad muchos-uno, y (c) "join-closed" (es decir, unión disjunta) wrt polytime reducibilidad de muchos.

Más formalmente, todos los idiomas. $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]$ esno cerrado bajo tales reducciones.)