Diferencia entre revisiones de «PSPACE»
m plantilla AP | categoría: |
m Correcciones menores, (WP:CEM) |
||
| Línea 1: | Línea 1: | ||
En [[complejidad computacional|teoría de la complejidad computacional]], la |
En [[complejidad computacional|teoría de la complejidad computacional]], la clase '''ESPACIOP''' (PSPACE en [[idioma inglés|inglés]]) es el conjunto de los [[problema de decisión|problemas de decisión]] que pueden ser resueltos por una [[máquina de Turing]] determinista en [[espacio polinomial]] y tiempo ilimitado. |
||
La definición no depende del carácter determinista de la máquina de Turing (esto es un corolario del [[teorema de Savitch]]). De manera que |
|||
Por el [[teorema de Savitch]], ESPACIONP = [[ESPACIOP]]. |
|||
:ESPACIOP = [[ESPACIONP]]. |
|||
El conjunto ESPACIOP es un subconjunto estricto del conjunto de [[lenguajes sensitivos al contexto]]. Las siguientes inclusiones han sido demostradas:(la [[inclusión estricta]] se denota ⊂): |
|||
:[[NC]] ⊆ [[Tiempo polinómico|P]] ⊆ [[NP]] ⊆ ESPACIOP |
|||
:[[NC]] ⊂ ESPACIOP ⊂ [[EXPSPACE]] |
|||
:[[ESPACIOP-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 dólares]]. 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 [[ESPACIOP-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. |
|||
{{Clases de complejidad}} |
{{Clases de complejidad}} |
||
{{esbozo de|informática}} |
|||
[[Categoría:Clases de complejidad]] |
[[Categoría:Clases de complejidad]] |
||
| ⚫ | |||
[[de:PSPACE]] |
|||
| ⚫ | |||
[[he:PSPACE]] |
|||
Revisión del 23:42 23 ago 2006
En teoría de la complejidad computacional, la clase ESPACIOP (PSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial y tiempo ilimitado.
La definición no depende del carácter determinista de la máquina de Turing (esto es un corolario del teorema de Savitch). De manera que
- ESPACIOP = ESPACIONP.
El conjunto ESPACIOP es un subconjunto estricto del conjunto de lenguajes sensitivos al contexto. Las siguientes inclusiones han sido demostradas:(la inclusión estricta se denota ⊂):
- ESPACIOP-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 un millón de dólares. 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 ESPACIOP-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.