Teorema de hierarquia de tempo

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 n² 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 Cook^[3] 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 Meyer^[4] 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

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

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

Afirmação editar

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 n² mas não em tempo n, já que n está em $o\left({\frac {n^{2}}{\log {n^{2}}}}\right)$ .

Prova editar

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

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 H_f 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)³ 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 H_f está nesta classe de complexidade de tempo e vamos tentar chegar em uma contradição.

Se H_f 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 H_f 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 H_f, 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 H_f, 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

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 eficiente^[6] 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

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

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 P ⊂ Exptime ⊂ 2-EXP ⊂ ... and NP ⊂ NEXPTIME ⊂ 2-NEXP ⊂ ....

Por exemplo, P ⊂ EXPTIME desde que P ⊆ DTIME(2ⁿ) ⊂ DTIME(2²ⁿ) ⊆ 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(n^k) para qualquer k fixo. Por exemplo, existem problemas solúveis em tempo n⁵⁰⁰⁰ mas não em tempo n⁴⁹⁹⁹. 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 P ≠ PSPACE, 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

↑ Hartmanis, J.; Stearns, R. E. (1 de maio de 1965). «On the computational complexity of algorithms». American Mathematical Society. Transactions of the American Mathematical Society. 117: 285–306. ISSN 0002-9947. JSTOR 1994208. MR 0170805. doi:10.2307/1994208 |primeiro1= e |primeiro= redundantes (ajuda)
↑ Hennie, F. C.; Stearns, R. E. (1966). «Two-Tape Simulation of Multitape Turing Machines». New York, NY, USA: ACM. J. ACM. 13 (4): 533–546. ISSN 0004-5411. doi:10.1145/321356.321362
↑ Cook, Stephen A. (1972). «A hierarchy for nondeterministic time complexity». Proceedings of the fourth annual ACM symposium on Theory of computing. STOC '72. Denver, Colorado, United States: ACM. pp. 187–192. doi:10.1145/800152.804913
↑ Seiferas, Joel I.; Fischer, Michael J.; Meyer, Albert R. (1978). «Separating Nondeterministic Time Complexity Classes». New York, NY, USA: ACM. J. ACM. 25 (1): 146–167. ISSN 0004-5411. doi:10.1145/322047.322061
↑ Stanislav, Žák (1983). «A Turing machine time hierarchy». Elsevier Science B.V. Theoretical Computer Science. 26 (3): 327–333. doi:10.1016/0304-3975(83)90015-4
↑ Luca Trevisan, Notes on Hierarchy Theorems, U.C. Berkeley

Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-X Pages 310–313 of section 9.1: Hierarchy theorems.
Christos Papadimitriou (1993). Computational Complexity 1st ed. [S.l.]: Addison Wesley. ISBN 0-201-53082-1 Section 7.2: The Hierarchy Theorem, pp. 143–146.

[1] Hartmanis, J.; Stearns, R. E. (1 de maio de 1965). «On the computational complexity of algorithms». American Mathematical Society. Transactions of the American Mathematical Society. 117: 285–306. ISSN 0002-9947. JSTOR 1994208. MR 0170805. doi:10.2307/1994208 |primeiro1= e |primeiro= redundantes (ajuda)

[2] Hennie, F. C.; Stearns, R. E. (1966). «Two-Tape Simulation of Multitape Turing Machines». New York, NY, USA: ACM. J. ACM. 13 (4): 533–546. ISSN 0004-5411. doi:10.1145/321356.321362

[3] Cook, Stephen A. (1972). «A hierarchy for nondeterministic time complexity». Proceedings of the fourth annual ACM symposium on Theory of computing. STOC '72. Denver, Colorado, United States: ACM. pp. 187–192. doi:10.1145/800152.804913

[4] Seiferas, Joel I.; Fischer, Michael J.; Meyer, Albert R. (1978). «Separating Nondeterministic Time Complexity Classes». New York, NY, USA: ACM. J. ACM. 25 (1): 146–167. ISSN 0004-5411. doi:10.1145/322047.322061

[5] Stanislav, Žák (1983). «A Turing machine time hierarchy». Elsevier Science B.V. Theoretical Computer Science. 26 (3): 327–333. doi:10.1016/0304-3975(83)90015-4

[6] Luca Trevisan, Notes on Hierarchy Theorems, U.C. Berkeley

[1]

[2]

[3]

[4]

[5]

[6]