Diferencia entre revisiones de «PSPACE»

4 bytes añadidos ,  hace 17 años
m
PSPACE --> ESPACIOP
m (PSPACE --> ESPACIOP)
m (PSPACE --> ESPACIOP)
:[[NC]] ⊂ ESPACIOP ⊂ [[EXPSPACE]]
 
:[[PSPACEESPACIOP-completo]] ⊆ ESPACIOP
 
En la primera línea hay tres inclusiones, y se sabe que [[NC]] ⊂ ESPACIOP, 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 sospecha también que la inclusión de la última línea es estricta.
 
Los problemas más difíciles en ESPACIOP son los del conjunto [[PSPACEESPACIOP-completo]].
 
El conjunto ESPACIOP se puede definir de forma equivalente como el conjunto de problemas que pueden ser decididos por una máquina de Turing alternante en tiempo polinómico.
30 917

ediciones