Teorema de hierarquia de tempo

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

Na teoria da complexidade computacional, os teoremas de hierarquia de tempo são importantes declarações sobre a limitação de tempo de computação de máquinas de Turing. Informalmente, estes teoremas dizem que com mais tempo, uma máquina de Turing pode resolver mais problemas. Por exemplo, existem problemas que podem ser resolvidos em tempo n2 mas não em tempo n.

O teorema de hierarquia de tempo para as máquinas de Turing determinísticas foi testado por Richard Stearns and Juris Hartmanis in 1965.1 Foi melhorado um ano depois quando F. C. Hennie and Richard Stearns aumentaram a eficiência da máquina de Turing universal.2 Como consequência, para cada classe de complexidade limitadas temporalmente, há uma outra classe de complexidade estritamente maior, e assim a hierarquia de tempo limitado de classes de complexidade não colapsam completamente. Mais especificamente, o teorema de hierarquia de tempo para máquinas de Turing determinísticas diz que para todas as funções de tempo construtível do tipo f(n), temos:

\operatorname{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right) \subsetneq \operatorname{DTIME}(f(n)).

O teorema de hierarquia de tempo para máquinas de Turing não-determinísticas foi provado originalmente por Stephen Cook3 em 1972. Foi melhorado e chegou a sua forma atual através de uma prova muito complexa realizada por Joel Seiferas, Michael Fischer, and Albert Meyer4 em 1978. Finalmente em 1983, Stanislav Žák alcançou os mesmo resultados com uma prova bem mais fácil, que é a ensinada nos dias de hoje.5 O teorema de hierarquia de tempo para máquinas de Turing não-determinísticas diz que se g(n) é uma função tempo construtível, e f(n+1) = o(g(n)), então

\operatorname{NTIME}(f(n)) \subsetneq \operatorname{NTIME}(g(n)).

O teorema análogo para o espaço é o teorema de hierarquia de espaço.

Base matemática[editar | editar código-fonte]

O teorema usa a noção de função de tempo construtível. Uma função f:\mathbb{N}\rightarrow\mathbb{N} é tempo construtível se existe uma máquina de Turing determinística que para todo n\in\mathbb{N}, se a máquina começa com uma entrada n, irá parar, precisamente, após f(n) passos. Todo polinómio com coeficientes inteiros não-negativos são tempo construtível, assim como as funções exponenciais do tipo 2^n.

Ideia da prova[editar | editar código-fonte]

Nós temos que provar que algumas classes de tempo, como a TIME(g(n)) podem ser estritamente maiores do que classes como a TIME(f(n)). Fazemos isso construindo uma máquina que não pode estar em TIME(f(n)), através do argumento de diagonalização de Cantor. E então, mostramos que a máquina está em TIME(g(n)), fazendo uma simulação da máquina.

Teorema de hierarquia de tempo determinístico[editar | editar código-fonte]

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

O teorema diz que: Se f(n) é uma função tempo construtível, então existe um problema de decisão, que não pode ser resolvido, no pior caso, em tempo determinístico f(n) mas pode ser resolvido, no pior caso, em tempo determinístico f(n)^2. Em outras palavras, a classe de complexidade Dtime(f(n)) é um subconjunto estrito de DTIME(f(n)^2). Note que f(n) é pelo menos n, uma vez que funções menores nunca serão tempo construtível.

Generalizando um pouco mais, podemos mostrar que se f(n) é tempo construtível, então \operatorname{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right) está devidamente contida em \operatorname{DTIME}(f(n)). Por exemplo, há problemas solúveis em tempo n2 mas não em tempo n, já que n está em o\left(\frac{n^2}{\log {n^2}}\right).

Prova[editar | editar código-fonte]

Nós incluímos aqui a prova que DTIME(f(n)) é um subconjunto estrito de DTIME(f(2n + 1)3) por ser mais simples. Veja na parte inferior desta seção para obter informações sobre como estender a prova para f(n)2.

Para provar isso, nós primeiramente definiremos uma linguagem como segue:

 H_f = \left\{ ([M], x)\ |\ M \ \mbox{aceita}\ x \ \mbox{em}\ f(|x|) \ \mbox{passos} \right\}.

Aqui, M máquina de Turing determinística, e x é a sua entrada (a configuração inicial de sua fita). [M] indica uma entrada que codifica a máquina de Turing M. Seja m do tamanho da tupla ([M], x).

Nós sabemos que podemos decidir um membro de Hf por meio de uma máquina de Turing determinística que calcula primeiro f(|x|), então escreve uma linha de 0s desse comprimento, e depois usa essa linha de 0s como um "clock" ou "contador" para simular M por no máximo essas quantidades de passos. A cada passo, a máquina de simulação precisa verificar a definição de M para decidir qual será a próxima ação. É seguro dizer que isto levará no máximo f(m)3 operações, logo:

 H_f \in \mathsf{TIME}(f(m)^3).

O resto da prova irá mostrar que:

 H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor ))

assim, se nós substituirmos 2n + 1 por m, teremos o resultado esperado. Vamos assumir que Hf está nesta classe de complexidade de tempo e vamos tentar chegar em uma contradição.

Se Hf está nesta classe de complexidade, significa que podemos construir uma máquina K que, dada uma descrição de máquina [M] e entrada x, decide se a tupla ([M], x) está em Hf dentro dos limites de  \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) .

Portanto, podemos usar esta máquina K para construir outra máquina, N, que leva a descrição da máquina [M] e roda K sobre a tupla ([M], [M]), e então aceita se e somente se K rejeita, e rejeita se K aceita. Se agora n é o comprimento da entrada para N, em seguida, m (o comprimento da entrada para K) é duas vezes n mais algum símbolo delimitador, logo m = 2n + 1. O tempo de execução de N é do tipo  \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) = \mathsf{TIME}(f( \left\lfloor (2n+1)/2 \right\rfloor )) = \mathsf{TIME}(f(n)).

Agora se nós alimentarmos [N] como entrada de si mesma (o que faz n ter tamanho [N]) e nos questionarmos se N aceita a sua própria descrição como entrada, temos que:

  • Se N aceita [N] (que sabemos que realiza em no máximo f(n) operações), isso significa que K rejeita ([N], [N]), logo ([N], [N]) não está em Hf, e portanto N não aceita [N] em f(n) passos. Contradição!
  • Se N rejeita [N] (que sabemos que realiza em no máximo f(n) operações), isso significa que K aceita ([N], [N]), logo ([N], [N]) está em Hf, e portanto N aceita [N] em f(n) passos. Contradição!

Concluímos daí que a máquina K não existe, e assim:

 H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )).

Extensão[editar | editar código-fonte]

O presente leitor deve ter percebido que a prova é simples pois nós escolhemos simular uma máquina de Turing simples para o qual podemos ter certeza que

 H_f \in \mathsf{TIME}(f(m)^3).

Tem sido mostrado que existe um modelo de simulação mais eficiente6 a qual estabelece que

 H_f \in \mathsf{TIME}(f(m) \log f(m))

uma vez que esse modelo de simulação é pouco envolvente, ele não será incluído aqui.

Teorema de hierarquia de tempo não-determinístico[editar | editar código-fonte]

Se g(n) é uma função tempo construtível, e f(n+1) = O(g(n)), então existe um problema de decisão que não pode ser resolvido em tempo não-determinístico f(n) mas pode ser resolvido em tempo não-determinístico g(n). Em outras palavras, a classe de complexidade NTIME(f(n)) é um subconjunto estrito de NTIME(g(n)).

Consequências[editar | editar código-fonte]

Os teoremas de hierarquias de tempo garantem que as versões determinísticas e não-determinísticas da hierarquia exponencial são hierarquias genuínas; em outras palavras PExptime2-EXP ⊂ ... and NPNEXPTIME2-NEXP ⊂ ....

Por exemplo, PEXPTIME desde que PDTIME(2n) ⊂ DTIME(22n) ⊆ EXPTIME.

O teorema também garante que há problemas em P requerendo grandes expoentes arbitrárias para serem resolvidos; em outras palavras, P não colapsa para DTIME(nk) para qualquer k fixo. Por exemplo, existem problemas solúveis em tempo n5000 mas não em tempo n4999. Este é um dos argumentos contra a tese de Cobham-Edmonds, a convenção de que P é uma classe prática de algoritmos. Se tal colapso ocorrer, nós podemos deduzir que PPSPACE, uma vez que um teorema bem conhecido diz que DTIME(f(n)) está estritamente contido em DSPACE(f(n)).

No entanto, os teoremas de hierarquia de tempo não fornecem meios de se relacionar complexidade determinística e não-determinística, ou complexidade de tempo e de espaço, logo eles não lançam nenhuma luz sobre as grandes questões não resolvidas da teoria da complexidade computacional: se P e NP, NP e PSPACE, PSPACE e EXPTIME, ou EXPTIME e NEXPTIME são iguais ou não.

Referencias[editar | editar código-fonte]

  1. J.. (1 May 1965) "On the computational complexity of algorithms". Transactions of the American Mathematical Society 117: 285–306. American Mathematical Society. DOI:10.2307/1994208. ISSN 00029947.
  2. (October 1966) "Two-Tape Simulation of Multitape Turing Machines". J. ACM 13 (4): 533–546. New York, NY, USA: ACM. DOI:10.1145/321356.321362. ISSN 0004-5411.
  3. Cook, Stephen A. (1972). "A hierarchy for nondeterministic time complexity" in STOC '72. Proceedings of the fourth annual ACM symposium on Theory of computing: 187–192, Denver, Colorado, United States: ACM. DOI:10.1145/800152.804913. 
  4. (January 1978) "Separating Nondeterministic Time Complexity Classes". J. ACM 25 (1): 146–167. New York, NY, USA: ACM. DOI:10.1145/322047.322061. ISSN 0004-5411.
  5. (October 1983) "A Turing machine time hierarchy". Theoretical Computer Science 26 (3): 327–333. Elsevier Science B.V.. DOI:10.1016/0304-3975(83)90015-4.
  6. Luca Trevisan, Notes on Hierarchy Theorems, U.C. Berkeley