Como sabemos, el isomorfismo gráfico está en NP pero no se sabe que sea NP-Completo o P-Completo. Me preguntaba si hay algún problema que se sabe que está en PSPACE pero no se sabe que es PSPACE-Complete y no se encuentra en PH.
cc.complexity-theory
complexity-classes
Tayfun Pay
fuente
fuente
Respuestas:
Se sabe que la teoría existencial de los reales está contenida en PSPACE, pero no se sabe si está contenida en PH. Así que tome la teoría existencial de los reales, o cualquiera de los muchos problemas equivalentes.
fuente
Cualquier problema de PP completo es trivial en PSPACE, pero, por supuesto, no se sabe que sea PSPACE completo. Tampoco sabemos si PP está contenido o no en PH, aunque del teorema de Toda se deduce que PH está contenido en P . Creo que lo mismo también se aplica a los problemas completos de #P .PP
fuente
Copiando mi comentario:
Si tenía la intención de solicitar un problema análogo a GI, entonces quizás esté solicitando un problema que no está en PH y no está completo en PSPACE. Los problemas completos para cualquier clase que no se sepa que está contenida en PH, pero que está contenida en PSPACE, funcionará como un ejemplo. Así que tome cualquier problema completo para BQP, QMA, PP, etc.
fuente
Cualquier problema que sea MP-Completo, la clase de problemas de decisión de tal manera que para alguna función #P f, la respuesta en la entrada x es 'sí' si y solo si el bit medio de f (x) es 1. [La definición es de Complejidad Zoo].
Se ha demostrado que PH ⊆ MP ⊆ PSPACE.
fuente
El problema de ParitySat es verificar si un problema SAT tiene un número impar de asignaciones satisfactorias. PH es reducible a ParitySAT a través de reducciones aleatorias por el trabajo de Toda. Este es un problema de decisión que está claramente estrictamente entre PH y PSACE a menos que el PH colapse.
fuente