Diferencia entre revisiones de «PSPACE»

2097 bytes añadidos ,  hace 12 años
sin resumen de edición
m (robot Añadido: ru:Класс PSPACE)
Sin resumen de edición
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(S(n) = aknk + ak−1nk−1 + . . . + a0 ) 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 = [[NPSPACE]]. Si un problema se resuelve mediante un algoritmo no determinista de complejidad espacial polinómica, también se puede resolver mediante un algoritmo determinista de complejidad espacial polinómica.
 
== DEFINICIÓN FORMAL ==
:ESPACIOP = [[ESPACIONP]].
 
En el caso de la complejidad espacial, se puede caracterizar la clase de lenguajes '''ESPACIOP''':
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 ⊂):
 
<math>\mbox{ESPACIOP} = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(n^k)</math>
:[[NC]] ⊆ [[Tiempo polinómico|P]] ⊆ [[NP]] ⊆ ESPACIOP
 
es decir, la unión de todas las clases de complejidad espacial polinómicas sobre Máquinas de Turing deterministas.
:[[NC]] ⊂ ESPACIOP ⊂ [[EXPSPACE]]
 
== RELACIÓN ENTRE OTRAS CLASES ==
:[[ESPACIOP-completo]] ⊆ ESPACIOP
 
Todos los problemas resolubles en tiempo polinómico con máquinas no deterministas (todos los problemas que están en [[NP]]) pueden resolverse en espacio polinómico, por lo tanto, '''ESPACIOP''' incluye [[NP]] y [[Co-NP]].
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 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.
Se conjetura que exista un conjunto de problemas que sean [[ESPACIOP-completo]]. Si lo hubiera y uno de ellos estuviera en [[NP]], entonces '''ESPACIOP=NP''', o si estuviera alguno de ellos en [[P]], entonces '''ESPACIOP=P'''.
 
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 ⊂):
Los problemas más difíciles en ESPACIOP son los del conjunto [[ESPACIOP-completo]].
 
:[[NC]]'''NL[[Tiempo polinómico|P]][[NP]] ⊆ ESPACIOP'''
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.
 
'''NL ⊂ ESPACIOP⊂ EXPSPACE'''
 
:[['''ESPACIOP-completo]]ESPACIOPPSPACE'''
En la primera línea hay tres inclusiones, y se sabe que [[NCNL]] ⊂ ESPACIOP, de manera que al menos una de las inclusiones es estricta, aunque se ha descubierto cualcuál 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]].
.
 
== OTRAS CARACTERÍSTICAS ==
 
Una característica alternativa de '''ESPACIOP''' es el conjunto de problemas decidibles por una [[maquina de Turing]] alternativa en tiempo polinomial, a veces llamadas '''APTIME''' o solamente '''AP'''.
 
Una característica lógica de '''ESPACIOP''' desde la teoría de la complejidad descriptiva es que son conjuntos de problemas expresados en segundo orden lógico con la adición de un operador de la [[clausura transitiva]]. Un [[cierre transitivo]] completo no es necesario; un cierre transitivo conmutativo es suficiente e incluso formas más débiles. La adicción de este operador hace distinguible el '''ESPACIOP''' del '''PH'''.
 
Un importante resultado de la teoría de la complejidad es que '''ESPACIOP''' puede ser caracterizada como todas las lenguas reconocidas por la presencia de un sistema interactivo de la prueba (interactive proof system), una definición de la clase '''IP'''. En este sistema, hay una demostración que intenta convencer aleatoriamente en [[tiempo polinomial]] para verificar que una cadena pertenece al lenguaje. Debe ser capaz de convencer al verificador con una elevada probabilidad, si la cadena está en el lenguaje, pero no debería ser capaz de convencer con una baja probabilidad, si la cadena no está en el lenguaje.
 
 
1

edición