时间层级定理(Time Hierarchy Theorem)

时间层级定理(Time Hierarchy Theorem)是计算复杂度理论中的基础分离结果。它断言:若给图灵机足够多的额外时间,就一定能解决更多问题。更准确地说,只要一个时间界比另一个时间界渐近地大得足够多,前者所定义的时间复杂度类就严格包含后者,存在只能在更多时间内解决的问题。

概述

该定理适用于确定型和非确定型图灵机,分别有对应的版本。它的意义在于,复杂度理论中许多类之间的分离都是开放问题,例如 P 是否等于 NP,而时间层级定理是少数能被严格证明的真分离之一,确保了复杂度类不会全部坍缩成一个。它保证了诸如指数时间严格强于多项式时间这样的直观事实。

核心原理

• 对角化方法:构造一台机器,让它在给定时间内模拟并故意与所有较低时间界的机器不同,从而定义一个较低界无法解决的问题。
• 可构造时间界:定理要求所用的时间界是时间可构造的,以便机器能自我限时。
• 存在对数级开销:确定型版本中,模拟带来的额外开销导致两个时间界之间需要一个对数因子的间隔。
• 严格包含:满足条件时,较大时间类真包含较小时间类。

应用场景

时间层级定理为复杂度类的层级结构提供了坚实基础。它直接推出多项式时间类 P 严格包含于指数时间类中,说明确实存在需要指数时间的可解问题。它也是理解为什么复杂度理论中类的划分有意义的关键,并为对角化这一证明技术提供了范例。

常见问题

问:它能帮助解决 P 与 NP 问题吗?答:不能直接解决。对角化式的层级定理无法区分 P 与 NP,现有证明表明单纯对角化不足以分离这两类。

问:为什么需要时间可构造这一条件?答:因为对角化机器必须能准确地为自己设定时间上限,若时间界无法被机器有效计算,构造就无法进行。