Beneficios para clases sintácticas y semánticas.

Esta es una publicación separada de Consecuencias de UP es igual a NP , y también una pregunta de seguimiento a las clases de complejidad semántica vs. sintáctica .

En la publicación anterior aprendimos sobre las clases semánticas y sintácticas . En pocas palabras, cuando una clase puede caracterizarse como una clase de lenguaje de hoja , entonces una clase es sintáctica si L 1 ∪ L 2 = Σ ∗ , es decir, aceptar el lenguaje L 1 es el complemento del rechazo del lenguaje L 2 ; de lo contrario lo llamamos una clase semántica. Uno puede ver que P , N P y P $\mathsf{L}[L_1|L_2]$$L_1 \cup L_2 = \Sigma^*$$L_1$$L_2$$\mathsf{P}$$\mathsf{NP}$$\mathsf{PP}$son clases sintácticas, mientras que clases como e I P son clases semánticas.$\mathsf{BPP}$$\mathsf{IP}$

Resultado clásico como y conjetura P ? = B P P ambos pueden verse a medida que las clases semánticas tienen caracterizaciones sintácticas. Me parece que las clases sintácticas son más fáciles de manejar, ya que tienen problemas naturales completos. También técnicas como la diagonalización son más fáciles de aplicar en clases sintácticas, ya que tienen una enumeración de máquina natural. Pero aún así B P P como una clase semántica parece tener propiedades mucho más agradable que la clase sintáctica P P .$\mathsf{PSPACE} = \mathsf{IP}$$\mathsf{P} \stackrel{?}{=} \mathsf{BPP}$$\mathsf{BPP}$$\mathsf{PP}$

¿Qué beneficios tenemos si tenemos una representación sintáctica de una clase semántica, o viceversa? ¿Existen resultados o técnicas de prueba que solo se aplican a las clases sintácticas / semánticas?

Aquí hay un par de ventajas.

1. $n^3$$=$$n^2$
2. Es más fácil crear oráculos que separen las clases sintácticas ya que solo necesita diagonalizar infinitamente a menudo y no le importa lo que suceda en las otras longitudes de entrada. Por el contrario, es más fácil colapsar las clases semánticas, ya que puede eliminar máquinas que no cumplan la promesa.

Creo que, en este nivel de generalidad, ya ha resaltado algunos de los principales valores de las clases sintácticas en la pregunta: tienen una enumeración de máquinas y, como consecuencia, tienen problemas naturales completos y uno puede hacer más fácilmente la diagonalización. Por supuesto, las clases semánticas específicas (como UP) pueden tener otros beneficios, pero para "sintáctico versus semántico" en general, creo que la enumeración de la máquina y sus consecuencias son el principal beneficio.

Creo que el beneficio de crear una clase semántica es poder aislar las respuestas que realmente deseas. Por ejemplo, en UP nos preocupa si hay una solución o cero soluciones y no nos importa si hay más de una solución. Creo que la clase semántica es una forma de ajustar las clases sintácticas.