30 917
ediciones
Diferencia entre revisiones de «PSPACE»
m
determinístico --> determinista
m (Corrección de enlace) |
m (determinístico --> determinista) |
||
|
En [[complejidad computacional|teoría de la complejidad computacional]], la clase '''PSPACE''' es el conjunto de los [[problema de decisión|problemas de decisión]] que pueden ser resueltos por una [[máquina de Turing]]
La definición no depende del
:PSPACE = [[NPSPACE]].
:[[PSPACE-completo]] ⊆ 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
Los problemas más
El conjunto PSPACE se puede definir de forma equivalente como el conjunto de problemas
{{Clases de complejidad}}
| |||