¿Es el tiempo cuasi polinomial en PSPACE?

14

Hice una búsqueda sobre esto, pero no pude encontrar una respuesta de ninguna manera.

Huck respondió por completo. Gracias :)

Tayfun Pay
fuente
1
¿Puedes mover tu "comentario dentro de la pregunta" a un comentario real?
Suresh Venkat
@Suresh, ¿no creo que haya suficiente espacio para ello? No estoy seguro.
Tayfun Pay
2
¿Puede quizás eliminar por completo la parte "comentario"? No creo que sea apropiado.
Jukka Suomela
1
Pon lo que puedas y quita el resto. Y publique esto en la respuesta de Huck. No es apropiado insertar un comentario de respuesta dentro de la pregunta original
Suresh Venkat

Respuestas:

27

Aquí hay un argumento simple que muestra que no se sabe que QP esté en PSPACE:

Supongamos . Luego tenemos P Q P P S P A C E , donde la primera inclusión es apropiada por el teorema de la jerarquía de tiempo.QPAGPAGSPAGUNCmiPAGQPAGPAGSPAGUNCmi

Esto separa a de P S P A C E , que no se sabe que se mantiene, por lo que tampoco se debe saber que Q P P S P A C E se mantiene.PAGPAGSPAGUNCmiQPAGPAGSPAGUNCmi

De hecho, tenemos que , pero Q P P S P A C E no separa las dos clases por el THT (como se indica en la pregunta )PAGSPAGUNCmiQPAGPAGSPAGUNCmimiXPAGQPAGPAGSPAGUNCmi

Huck Bennett
fuente