DSPACE

Em complexidade computacional, DSPACE ou simplesmente SPACE é um recurso computacional descrevendo a disponibilidade de memória para uma máquina de Turing. Este representa o quantidade total de memória que um computador físico "normal" precisaria para solucionar um dado problema computacional com um algoritmo. É uma das mais estudadas medidas de complexidade, dada sua relevância para solução de um problema real: qual é a quantidade de memória necessária para resolver um dado problema com um dado algoritmo.

Classes de Complexidade

A medida de DSPACE é utilizada para definir classes de complexidade, conjunto de todos os problemas de decisão que podem ser solucionados dada uma certa quantidade de memória. Para uma função f(n), existe uma classe de complexidade SPACE(f(n)), o conjunto dos problemas de decisão que podem ser solucionados com uma máquina de Turing determinística utilizando espaço O(f(n)). Não existe restrição ao tempo computacional que pode ser utilizado, mas pode haver outro tipo de restrição em outras medidas de complexidade (tal como alternação).

Diversas classes de complexidade podem ser definidas em termos do DSPACE. Tais como:

• REG = DSPACE(O(1)), onde REG é a classe das linguagens regulares. De fato, REG = DSPACE(o(log log n)) (isto é, Ω(log log n) espaço é requerido para reconhecer qualquer linguagem não regular).
• L = DSPACE(O(log n))
• PSPACE = $\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(n^{k})$
• EXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})$

Modelos de Máquinas

DSPACE é tradicionalmente medida em uma máquina de Turing determinística. Diversos problemas de complexidade espacial são sublineares, isto é, menores do que a entrada que recebem. Logo, "carregar" o algoritmo para o tamanho da entrada ou saída não captura a quantidade de memória que realmente é utilizada. Este problema é solucionado definindo uma máquina de Turing multi-fitas com entrada e saída onde a fita de entrada nunca pode ser escrita e a fita de saída nunca pode ser lida. Isto permite que classes de espaço menores, tal como L (espaço logarítmico), sejam definidas em termos da quandidade de espaço utilizado para todas as fitas (excluíndo-se as fitas de entrada e saída, que não são fitas de trabalho).

Teorema da Hierarquia

A teoria hierárquica do espaço mostra que, para cada função contrutível no espaço $f:\mathbb {N} \to \mathbb {N}$, existe uma linguagem L que decidível em espaço $O(f(n))$ mais não em espaço $o(f(n))$. Veja teoria hierárquica do espaço para maiores detalhes.

Relação com com complexidade de classes

DSPACE é o equivalente determinístico do NSPACE, a classe de espaço de memória em uma máquina de Turing não-determinística. Pelo Teorema de Savitch, temos que

${\mbox{DSPACE}}[s(n)]\subseteq {\mbox{NSPACE}}[s(n)]\subseteq {\mbox{DSPACE}}[(s(n))^{2}].$

NTIME é relacionado com DSPACE da seguinte maneira. Para cada cada função construtível no tempo t(n), temos

${\mbox{NTIME}}(t(n))\subseteq {\mbox{DSPACE}}(t(n))$.

Bibliografia

• Michael Sipser (2006). «Sections 8.14&ndash». Introdução à Teoria da Computação. [S.l.]: THOMSON. pp. 324–326. ISBN 0-534-95097-3