跳转到内容

时间阶层定理

维基百科,自由的百科全书

计算复杂度理论内,时间阶层定理(Time hierarchy theorems)是一个有关图灵机时间限制上面一系列重要的定理。用不大正式的说法解释,这理论告诉我们图灵机在给予更多时间之后,保证能解决更多的问题。

举例:必然存在问题是图灵机可以用n2的时间解决,但是不能用n的时间解决。

参考资料