Teorema de hierarquia de espaço

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

Formalmente, a função f:\mathbb{N} \longrightarrow \mathbb{N} é espaço construtível se f(n) \ge \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[editar | editar código-fonte]

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 } \le 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[editar | editar código-fonte]

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[editar | editar código-fonte]

Corolário 1[editar | editar código-fonte]

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[editar | editar código-fonte]

Para quaisquer dois números Reais 0 \leq a_1 < a_2, SPACE(n^{a_1}) \subset SPACE(n^{a_2}).

Corolário 3[editar | editar código-fonte]

NL \subset PSPACE.

Prova[editar | editar código-fonte]

O teorema de Savitch mostra que NL \subseteq SPACE(\log^2n), enquanto que o teorema de hierarquia de espaço mostra que SPACE(\log^2n) \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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]