En teoria de la complexitat, la classe de complexitat DSPACE(f(n)) o SPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida determinista de la classe NSPACE.
Diverses classe de complexitat es defineixen en funció de DSPACE:
REG = DSPACE(O(1)). L = DSPACE(O(log n)) PSPACE = EXPSPACE =
Relació amb d'altres classes DSPACE és la contrapart determinística de NSPACE, la classe en espai de memòria amb màquines de Turing no determinista. Pel teorema de Savitch, es te:NTIME està relacionada amb DSPACE de la següent manera: sigui t(n) una funció construïble, es te:
Referències
Categoria:Complexitat computacional Categoria:Classes de complexitat