Diferencia entre revisiones de «PSPACE»

26 bytes añadidos ,  hace 11 años
m
corrección de fórmula
(desambiguación de enlaces)
m (corrección de fórmula)
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 polinomial''' (<math>S(n) = aknka_{k} + ak−1nk−1n^{k} + .a_{k-1} .n^{k-1} + .\dots + a0a_{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.
1208

ediciones