¿Existe un oráculo

Antecedentes

Sabemos que . $P^{\#P} \subseteq PSPACE$

Además, se conoce a partir del teorema de Toda que . $PH \subseteq P^{\#P}$

Para obtener más información sobre , consulte aquí: https://en.wikipedia.org/wiki/Sharp-P $\#P$

Pregunta

¿Existe un oráculo tal que ? $A$ $(P^{\#P})^{A} \neq PSPACE^{A}$

cc.complexity-theory complexity-classes oracles relativization pspace Michael Wehar
fuente

A = PSPACE

$A=\textrm{PSPACE}$

{PSPACE}^{PSPACE} = PSPACE

$\textrm{PSPACE}^{\textrm{PSPACE}} = \textrm{PSPACE}$

@MichaelLampis Sí, si cuentas el espacio en la cinta de consulta, ¡eso me parece correcto! :)

Michael Wehar

¡Genial, muchas gracias por señalarlo! Modifiqué la pregunta eliminando la parte más fácil sobre encontrar un oráculo donde son iguales. :)

Michael Wehar

Hay un oráculo que separa PP del PSPACE: Jacobo Toran, una técnica combinatoria para separar las clases de complejidad de conteo, ICALP 1989. El mejor resultado para P ^ PP que conozco es un resultado condicional de Heribert Vollmer: Relacionando el tiempo polinomial a una profundidad constante. TCS, 207: 159-170, 1998.

Markus Bläser

@ MarkusBläser Creo que deberías publicar esto como respuesta.

Emil Jeřábek

Respuestas:

A petición popular, aquí está mi comentario como respuesta:

$\mathrm{PP}$ $\mathrm{PSPACE}$ $\mathrm{P}^\mathrm{PP}$

Markus Bläser
fuente

P^{P P} = P^{# P}

$P^{PP} = P^{\#P}$

P^{P P} \subseteq P^{# P}

$P^{PP} \subseteq P^{\#P}$

Sí, el complejo zoológico dice que son iguales. Además, creo recordar haber probado esto en un curso de teoría de la complejidad hace unos años como ejercicio. :)

Michael Wehar

El complejo zoológico también dice que mi pregunta principal es un problema abierto. Lo siento, no me di cuenta de eso. Pensé que tal vez alguien por ahí lo había resuelto.

Michael Wehar