DSPACE

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.

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada.

Este artículo trata sobre la clase de complejidad computacional. Para el paquete de software, véase DSpace.

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

${\displaystyle {\mbox{PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(n^{k})}$

• Datos: Q1155722