| rdfs:comment
| - 在計算複雜度理論內，時間階層定理（Time hierarchy theorems）是一個有關圖靈機時間限制上面一系列重要的定理。用不大正式的說法解釋，這理論告訴我們圖靈機在給予更多時間之後，保證能解決更多的問題。 舉例：必然存在問題是圖靈機可以用n2的時間解決，但是不能用n的時間解決。 (zh)
- En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede resolver más problemas. Por ejemplo, hay problemas que pueden ser solucionados en tiempo O(n2) pero no en O(n). . Los teoremas análogos para espacio son los . Para el caso de clases de complejidad probabilística acotada en el tiempo no hay teoremas similares, salvo que la clase tenga también . (es)
- In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time. . . The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of advice. (en)
- 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 análogo para o espaço é o teorema de hierarquia de espaço. (pt)
|
| has abstract
| - En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede resolver más problemas. Por ejemplo, hay problemas que pueden ser solucionados en tiempo O(n2) pero no en O(n). El teorema de la jerarquía temporal para máquinas de Turing deterministas fue probado por Richard Stearns y Juris Hartmanis. Como consecuencia, para cada clase de complejidad acotada temporalmente, hay otra clase de complejidad estrictamente mayor, tal que la jerarquía de acotación temporal para clases de complejidad converja por completo. Más concretamente, el teorema de jerarquía temporal para máquinas de Turing deterministas dice que para toda función computable , :. El teorema de jerarquía temporal para máquinas de Turing no deterministas fue probado por Stephen Cook. El teorema de la jerarquía temporal para máquinas de Turing no deterministas dice que si g(n) es una función computable, y f(n+1) = o(g(n)), entonces . Los teoremas análogos para espacio son los . Para el caso de clases de complejidad probabilística acotada en el tiempo no hay teoremas similares, salvo que la clase tenga también . (es)
- In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time. The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the Universal Turing machine. Consequent to the theorem, for every deterministic time-bounded complexity class, there is a strictly larger time-bounded complexity class, and so the time-bounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all time-constructible functions f(n), . The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972. It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978. Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today. The time hierarchy theorem for nondeterministic Turing machines states that if g(n) is a time-constructible function, and f(n+1) = o(g(n)), then . The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of advice. (en)
- 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. Foi melhorado um ano depois quando F. C. Hennie and Richard Stearns aumentaram a eficiência da máquina de Turing universal. 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 , temos: . O teorema de hierarquia de tempo para máquinas de Turing não-determinísticas foi provado originalmente por Stephen Cook 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 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. 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 . O teorema análogo para o espaço é o teorema de hierarquia de espaço. (pt)
- 在計算複雜度理論內，時間階層定理（Time hierarchy theorems）是一個有關圖靈機時間限制上面一系列重要的定理。用不大正式的說法解釋，這理論告訴我們圖靈機在給予更多時間之後，保證能解決更多的問題。 舉例：必然存在問題是圖靈機可以用n2的時間解決，但是不能用n的時間解決。 (zh)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)