DSPACE

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En teoría de la complejidad computacional, la clase de complejidad DSPACE(f(n)) o SPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en espacio O(f(n)) y tiempo ilimitado. Es la contrapartida determinista de la clase NSPACE.

La clase de complejidad PSPACE puede definirse en términos de DSPACE como:

\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(n^k)