Diferencia entre revisiones de «PSPACE»
Contenido eliminado Contenido añadido
Traducción de en: |
m Corrección de enlace |
||
Línea 11:
:[[NC]] ⊂ PSPACE ⊂ [[EXPSPACE]]
:[[PSPACE-
En la primera línea hay tres inclusiones, y se sabe que [[NC]] ⊂ PSPACE, de manera que al menos una de las inclusiones es estricta, aunque so se ha descubierto cual de ellas lo es. Se sospecha que las tres son inclusiones estrictas. Una solución al problema de saber si las clases P y NP son distintas vale [[Clay Mathematics Institute|un millón de dolares]]. Se sostecha también que la inclusión de la última línea es estricta.
Los problemas más dificiles en PSPACE son los del conjunto [[PSPACE-
El conjunto PSPACE se puede definir de forma equivalente como el conjunto de problemas decidibles por una máquina de Turing alternante en tiempo polinómico.
{{Clases de complejidad}}
[[
[[en:PSPACE]]
| |||