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

,

onde SPACE pode ser tanto DSPACE quanto NSPACE.

Afirmação[editar | editar código-fonte]

Formalmente, a função é espaço construtível se e existe uma máquina de Turing que computa a função no espaço quando começa com um entrada , onde 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 , existe uma linguagem que é decidível em espaço mas não em espaço .

Prova[editar | editar código-fonte]

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

Agora, para qualquer máquina que decida a linguagem em espaço , irá diferenciar em pelo menos um ponto sobre a linguagem de , previamente designada como . O algoritmo que decide a linguagem é da forma:

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

Note que no passo 3, a execução é limitada para passos para se evitar o caso em que não pára sobre a entrada . Ou seja, o caso onde consome espaço 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 , , onde (n) é o((n)) e é espaço construtível, SPACE((n)) SPACE((n)).

Este corolário nos permite separar várias classes de complexidade de espaço. Qualquer função é espaço construtível para qualquer número Natural k. Portanto, para qualquer dois números Naturais podemos provar que SPACE() SPACE(). 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 SPACE() SPACE().

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

NL PSPACE.

Prova[editar | editar código-fonte]

O teorema de Savitch mostra que NL SPACE(), enquanto que o teorema de hierarquia de espaço mostra que SPACE( SPACE(). Assim, ficamos com este corolário, juntamente com o fato de que TQBF 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 NPSPACE, e pelo teorema de Savitch para mostrar que PSPACE = NPSPACE.

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

PSPACE 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]