¿Existe un oráculo

8

Antecedentes

Sabemos que .P#PPSPACE

Además, se conoce a partir del teorema de Toda que .PHP#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 ( P # P ) AP S P A C E A ?A(P#P)APSPACEA

Michael Wehar
fuente
3
A=PSPACEPSPACEPSPACE=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
55
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
1
@ MarkusBläser Creo que deberías publicar esto como respuesta.
Emil Jeřábek

Respuestas:

6

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

PPPSPACEPPP

Markus Bläser
fuente
PPP=P#P
PPPP#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
2
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