Diferencia entre revisiones de «PSPACE»

5 bytes añadidos ,  hace 9 años
m
sin resumen de edición
m (Bot: Moviendo 13 enlaces interlingüisticos a d:Q500716 en Wikidata)
mSin resumen de edición
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]] determinista en '''espacio polinomialde polinomios''' (<math>S(n) = a_{k} n^{k} + a_{k-1} n^{k-1} + \dots + a_{0} </math>) 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 PSPACE = [[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.
== Otras características ==
 
Una característica alternativa de '''PSPACE''' es el conjunto de problemas decidibles por una [[máquina de Turing]] alternativa en [[tiempo polinomialpolinómico]], a veces llamadas '''APTIME''' o solamente '''AP'''.
 
Una característica lógica de '''PSPACE''' 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 '''PSPACE''' del '''PH'''.
 
Un importante resultado de la teoría de la complejidad es que '''PSPACE''' 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 (clase de complejidad)|IP]]. En este sistema, hay una demostración que intenta convencer aleatoriamente en [[tiempo polinomial]]polinómico 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.
 
[[Categoría:Clases de complejidad]]
121 932

ediciones