b'\n_START_ARTICLE_\nTeorema de hierarquia de tempo\n_START_SECTION_\nBase matem\xc3\xa1tica\n_START_PARAGRAPH_\nO teorema usa a no\xc3\xa7\xc3\xa3o de fun\xc3\xa7\xc3\xa3o de tempo construt\xc3\xadvel. Uma fun\xc3\xa7\xc3\xa3o  \xc3\xa9 tempo construt\xc3\xadvel se existe uma m\xc3\xa1quina de Turing determin\xc3\xadstica que para todo , se a m\xc3\xa1quina come\xc3\xa7a com uma entrada n, ir\xc3\xa1 parar, precisamente, ap\xc3\xb3s  passos. Todo polin\xc3\xb3mio com coeficientes inteiros n\xc3\xa3o-negativos s\xc3\xa3o tempo construt\xc3\xadvel, assim como as fun\xc3\xa7\xc3\xb5es exponenciais do tipo .\n_START_SECTION_\nIdeia da prova\n_START_PARAGRAPH_\nN\xc3\xb3s 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\xc3\xa1quina que n\xc3\xa3o pode estar em TIME(f(n)), atrav\xc3\xa9s do argumento de diagonaliza\xc3\xa7\xc3\xa3o de Cantor. E ent\xc3\xa3o, mostramos que a m\xc3\xa1quina est\xc3\xa1 em TIME(g(n)), fazendo uma simula\xc3\xa7\xc3\xa3o da m\xc3\xa1quina.\n_START_SECTION_\nAfirma\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nO teorema diz que: Se  \xc3\xa9 uma fun\xc3\xa7\xc3\xa3o tempo construt\xc3\xadvel, ent\xc3\xa3o existe um problema de decis\xc3\xa3o, que n\xc3\xa3o pode ser resolvido, no pior caso, em tempo determin\xc3\xadstico  mas pode ser resolvido, no pior caso, em tempo determin\xc3\xadstico . Em outras palavras, a classe de complexidade Dtime \xc3\xa9 um subconjunto estrito de DTIME. Note que  \xc3\xa9 pelo menos n, uma vez que fun\xc3\xa7\xc3\xb5es menores nunca ser\xc3\xa3o tempo construt\xc3\xadvel._NEWLINE_Generalizando um pouco mais, podemos mostrar que se  \xc3\xa9 tempo construt\xc3\xadvel, ent\xc3\xa3o  est\xc3\xa1 devidamente contida em . Por exemplo, h\xc3\xa1 problemas sol\xc3\xbaveis em tempo n\xc2\xb2 mas n\xc3\xa3o em tempo n, j\xc3\xa1 que n est\xc3\xa1 em .\n_START_SECTION_\nTeorema de hierarquia de tempo n\xc3\xa3o-determin\xc3\xadstico\n_START_PARAGRAPH_\nSe g(n) \xc3\xa9 uma fun\xc3\xa7\xc3\xa3o tempo construt\xc3\xadvel, e f(n+1) = O(g(n)), ent\xc3\xa3o existe um problema de decis\xc3\xa3o que n\xc3\xa3o pode ser resolvido em tempo n\xc3\xa3o-determin\xc3\xadstico f(n) mas pode ser resolvido em tempo n\xc3\xa3o-determin\xc3\xadstico g(n). Em outras palavras, a classe de complexidade NTIME(f(n)) \xc3\xa9 um subconjunto estrito de NTIME(g(n)).\n_START_SECTION_\nConsequ\xc3\xaancias\n_START_PARAGRAPH_\nOs teoremas de hierarquias de tempo garantem que as vers\xc3\xb5es determin\xc3\xadsticas e n\xc3\xa3o-determin\xc3\xadsticas da hierarquia exponencial s\xc3\xa3o hierarquias genu\xc3\xadnas; em outras palavras P \xe2\x8a\x82 Exptime \xe2\x8a\x82 2-EXP \xe2\x8a\x82 ... and NP \xe2\x8a\x82 NEXPTIME \xe2\x8a\x82 2-NEXP \xe2\x8a\x82 ...._NEWLINE_Por exemplo, P \xe2\x8a\x82 EXPTIME desde que P \xe2\x8a\x86 DTIME(2\xe2\x81\xbf) \xe2\x8a\x82 DTIME(2\xc2\xb2\xe2\x81\xbf) \xe2\x8a\x86 EXPTIME._NEWLINE_O teorema tamb\xc3\xa9m garante que h\xc3\xa1 problemas em P requerendo grandes expoentes arbitr\xc3\xa1rias para serem resolvidos; em outras palavras, P n\xc3\xa3o colapsa para DTIME(n\xe1\xb5\x8f) para qualquer k fixo. Por exemplo, existem problemas sol\xc3\xbaveis em tempo n\xe2\x81\xb5\xe2\x81\xb0\xe2\x81\xb0\xe2\x81\xb0 mas n\xc3\xa3o em tempo n\xe2\x81\xb4\xe2\x81\xb9\xe2\x81\xb9\xe2\x81\xb9. Este \xc3\xa9 um dos argumentos contra a tese de Cobham-Edmonds, a conven\xc3\xa7\xc3\xa3o de que P \xc3\xa9 uma classe pr\xc3\xa1tica de algoritmos. Se tal colapso ocorrer, n\xc3\xb3s podemos deduzir que P \xe2\x89\xa0 PSPACE, uma vez que um teorema bem conhecido diz que DTIME(f(n)) est\xc3\xa1 estritamente contido em DSPACE(f(n))._NEWLINE_No entanto, os teoremas de hierarquia de tempo n\xc3\xa3o fornecem meios de se relacionar complexidade determin\xc3\xadstica e n\xc3\xa3o-determin\xc3\xadstica, ou complexidade de tempo e de espa\xc3\xa7o, logo eles n\xc3\xa3o lan\xc3\xa7am nenhuma luz sobre as grandes quest\xc3\xb5es n\xc3\xa3o resolvidas da teoria da complexidade computacional: se P e NP, NP e PSPACE, PSPACE e EXPTIME, ou EXPTIME e NEXPTIME s\xc3\xa3o iguais ou n\xc3\xa3o.'