DSPACE

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «DSPACE» – noticias · libros · académico · imágenes Este aviso fue puesto el 22 de abril de 2019.

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:

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