Teorema de hierarquia de espaço

Na teoria da complexidade computacional, o teorema de hierarquia de espaço é resultado da separação que mostra que tanto as máquinas determinísticas quanto as não-determinísticas podem resolver mais problemas em mais espaço (assintoticamente), sob certas condições. Por exemplo, uma máquina de Turing determinística pode resolver mais problema de decisão em espaço n log n do que em espaço n. O teorema análogo para o tempo é o teorema de hierarquia de tempo.

A base para os teoremas de hierarquia reside na intuição de que com mais espaço ou com mais tempo vem a capacidade de computar mais funções (ou decidir mais linguagens). Os teoremas de hierarquia são utilizados para demonstrar que as classes de complexidade de tempo e de espaço, formam uma hierarquia onde classes com limitantes menores contém menos linguagens do que aquelas com limitantes maiores. Aqui vamos definir e provar o teorema de hierarquia do espaço.

Este teorema depende do conceito de função espaço construtível. O teorema de hierarquia do espaço determinístico e não-determinístico assumem que para todas as funções espaço construtível f(n), que

$\operatorname {SPACE} \left(o(f(n))\right)\subsetneq \operatorname {SPACE} (f(n))$,

onde SPACE pode ser tanto DSPACE quanto NSPACE.

Afirmação

Formalmente, a função $f:\mathbb {N} \longrightarrow \mathbb {N}$ é espaço construtível se $f(n)\geq \log ~n$ e existe uma máquina de Turing que computa a função $f(n)$ no espaço $O(f(n))$ quando começa com um entrada $1^{n}$, onde $1^{n}$ representa uma string de n 1s. Muitas das funções comuns que nós trabalhamos são espaço construtível, inclusive as polinomiais, as exponenciais e as logarítmicas.

Para todas as funções espaço construtíveis do tipo $f:\mathbb {N} \longrightarrow \mathbb {N}$, existe uma linguagem $L$ que é decidível em espaço $O(f(n))$ mas não em espaço $o(f(n))$.

Prova

O objetivo aqui é definir uma linguagem que possa ser decidida em espaço $O(f(n))$ mas não em espaço $o(f(n))$. Aqui definimos a linguagem $L$:

$L=\{~(\langle M\rangle ,10^{k}):M{\mbox{ rejeita }}(\langle M\rangle ,10^{k}){\mbox{ usando um espaço }}\leq f(|\langle M\rangle ,10^{k}|)~\}$

Agora, para qualquer máquina $M$ que decida a linguagem em espaço $o(f(n))$, $L$ irá diferenciar em pelo menos um ponto sobre a linguagem de $M$, previamente designada como $(\langle M\rangle ,10^{k})$. O algoritmo que decide a linguagem $L$ é da forma:

1. Para a uma entrada $x$, compute $f(|x|)$ usando espaço construtibilidade, e marque as $f(|x|)$ células da fita. Sempre que for feita uma tentativa de usar mais do que $f(|x|)$ células, rejeite.
2. Se $x$ não é da forma $\langle M\rangle ,10^{k}$ para alguma máquina $M$, rejeite.
3. Simule $M$ para a entrada $x$ por pelo menos $2^{f(|x|)}$ passos (utilizando espaço $f(|x|)$). Se a simulação tentar usar um espaço maior do que $f(|x|)$ ou realizar mais do que $2^{f(|x|)}$ operações, então rejeite.
4. Se $M$ aceita $x$ durante a simulação, então rejeite; caso contrário, aceite.

Note que no passo 3, a execução é limitada para $2^{f(|x|)}$ passos para se evitar o caso em que $M$ não pára sobre a entrada $x$. Ou seja, o caso onde $M$ consome espaço $O(f(x))$ como requerido, mas roda por um tempo infinito.

Comparações e Melhorias

O teorema de hierarquia do espaço é mais forte do que o seu análogo, o teorema de hierarquia do tempo, de várias maneiras:

• Ele precisa apenas de s(n) para ser pelo menos log n ao invés de pelo menos n.
• Ele pode separar classes com qualquer diferença assintótica, enquanto que o teorema de hierarquia do tempo requer o uso de um fator logarítmico para separá-las.
• Ele requer que as funções sejam apenas espaço construtível e não tempo construtível.

Parece ser bem mais fácil separar classes de complexidade de espaço do que classes de complexidade de tempo. Certamente, enquanto que o teorema de hierarquia de tempo tem mostrado poucos avanços memoráveis desde a sua criação, o teorema de hierarquia de espaço não determinístico tem pelo menos uma importante melhoria descrito por Viliam Geffert em seu artigo de 2003, "Teorema de hierarquia do espaço revisado". Este trabalho fez várias generalizações marcantes do teorema:

• Ele diminui a necessidade de espaço construtibilidade. Ao invés de meramente separar a união das classes SPACE(O(s(n)) e SPACE(o(s(n)), ele separa SPACE(f(n)) de SPACE(g(n)) onde f(n) é uma função O(s(n)) arbitrária e g(n) é a função computável o(s(n)). Estas funções não precisam ser espaço construtível ou nem mesmo uma crescente monotônica.
• Ele identifica uma linguagem unária, ou linguagem de contagem, que está em uma classe mas não na outra. No teorema original, a linguagem de separação era arbitrária.
• Ele não necessita de s(n) para ser pelo menos log n; ele pode ser qualquer função não-determinística totalmente espaço construtível.

Corolários

Corolário 1

Para quaisquer duas funções $f_{1}$, $f_{2}:\mathbb {N} \longrightarrow \mathbb {N}$, onde $f_{1}$(n) é o($f_{2}$(n)) e $f_{2}$ é espaço construtível, SPACE($f_{1}$(n)) $\subset$ SPACE($f_{2}$(n)).

Este corolário nos permite separar várias classes de complexidade de espaço. Qualquer função $n^{k}$ é espaço construtível para qualquer número Natural k. Portanto, para qualquer dois números Naturais $k_{1}<k_{2}$ podemos provar que SPACE($n^{k_{1}}$) $\subset$ SPACE($n^{k_{2}}$). Podemos estender essa ideia para números Reais (corolário 2). Isto demonstra a hierarquia detalhada dentro da classe PSPACE.

Corolário 2

Para quaisquer dois números Reais 0 $\leq a_{1}<a_{2},$ SPACE($n^{a_{1}}$) $\subset$ SPACE($n^{a_{2}}$).

Corolário 3

NL $\subset$ PSPACE.

Prova

O teorema de Savitch mostra que NL $\subseteq$ SPACE($\log ^{2}n$), enquanto que o teorema de hierarquia de espaço mostra que SPACE($\log ^{2}n)\subsetneq$ SPACE($n$). Assim, ficamos com este corolário, juntamente com o fato de que TQBF $\notin$ NL pois TQBF é PSPACE-completo.

Este corolário 3 também pode ser usado pelo teorema de hierarquia de espaço não-determinístico para mostrar que NL $\subset$ NPSPACE, e pelo teorema de Savitch para mostrar que PSPACE = NPSPACE.

Corolário 4

PSPACE $\subset$ EXPSPACE.

Este último corolário mostra a existência de problemas decidíveis que são intratáveis. Em outras palavras, o procedimento de decisão deles obrigatoriamente usa mais do que espaço polinomial.

Corolário 5

Há problemas em PSPACE que requerem um expoente arbitrariamente grande para se resolver, por isso PSPACE não entrar em colapso a DSPACE (nk) para alguma constante k.

Referências

• Luca Trevisan. Notes on Hierarchy Theorems. Handout 7. CS172: Automata, Computability and Complexity. U.C. Berkeley. April 26, 2004.
• Viliam Geffert. Space hierarchy theorem revised. Theoretical Computer Science, volume 295, number 1-3, p.171-187. February 24, 2003.
• Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-X  Pages 306–310 of section 9.1: Hierarchy theorems.
• Christos Papadimitriou (1993). Computational Complexity 1st edition ed. [S.l.]: Addison Wesley. ISBN 0-201-53082-1  Section 7.2: The Hierarchy Theorem, pp.143–146.