Complejidad sintáctica Clase

11

Se sabe que algunas clases de complejidad sintáctica (no relativizadas) entre y P S P A C E tienen la siguiente propiedad, PC o N PU SC = PP PP S P A C E . Me pregunto si existe una clase de complejidad sintáctica (no relativizada) X tal que P PXP S P A C EPPSPACEPCoNPUSC=PPPPSPACEXPPXPSPACE? ¿Cuáles son las implicaciones de la existencia o no existencia de complejidad clase ? X

Tayfun Pay
fuente
77
Primero, ¿presumiblemente quiere una clase que se cree que se encuentra estrictamente entre PP y PSPACE? De lo contrario, PP funciona, al igual que PSPACE. En segundo lugar, es difícil hablar sobre las implicaciones de la existencia de una clase de complejidad de este tipo a menos que especifique lo que cuenta como una clase de complejidad. Por ejemplo, si PP \ neq PSPACE, por Ladner hay un lenguaje L en PSPACE que es PP-hard y no PSPACE-complete. Si tomamos el cierre de L bajo reducciones de muchos, la "clase" resultante satisface su pregunta. Pero claramente esto no tiene consecuencias adicionales más allá de PP \ neq PSPACE ...
Joshua Grochow
1
@JoshuaGrochow ¡Gracias! ¿Qué tal si pero PP S P A C E . ¿Podemos obtener otra clase de Ladner? P=PPPPSPACE
Tayfun Pay
1
AmpBAmpCmpB

Respuestas:

14

Una de esas clases es la jerarquía de conteo . Se define como la unión de una jerarquía que se define de manera similar a la jerarquía polinómica:CH

  • C0P:=PP ,
  • Ci+1P:=PPCiP
  • CH:=iCiP

La jerarquía de conteo tiene una buena caracterización sintáctica debido a H. Vollmer y K. Wagner "Caracterizaciones teóricas de recursión de clases de complejidad de funciones de conteo", Theoretical Computer Science 163: 245-258, 1996 : es el conjunto de - - funciones valoradas en el cierre de funciones aritméticas básicas bajo composición y sumas acotadas.CH010,1,+,,

Jan Johannsen
fuente
Digo específicamente no relativizado ... También hay#P#NP...
Tayfun Pay
66
@TayfunPay: El párrafo final muestra que puede recibir una caracterización sin el uso de oráculos ... ¿qué, precisamente, quieres decir con "no relativizado"? ¿Quieres una caracterización de "máquina sin oráculo"? ¿Una caracterización en lenguaje hoja?CH
Joshua Grochow
2
De hecho es correcto. Ok
Tayfun paga el