动机
给机器更多时间,应当能让它解决更多问题,但证明必须面对一个障碍:模拟器在解释被模拟的机器时,本身也要花费时间。若恰好使用某台所谓更快的机器所允许的时间来做对角化,这笔模拟开销就可能耗尽全部预算。确定性时间层级定理留出一个对数量级的间隙,其大小足以吸收这笔开销,然后再翻转被模拟机器的答案。
我们把所用的模拟事实作为背景陈述,并通过显式的填充与量词来证明对角化论证。
定义
对函数 , 是指能被确定性多带图灵(Turing)机在 时间内判定的语言类。此处称函数 是时间可构造的,若存在一台确定性时钟机器,给定长度为 的一元输入,恰好运行 步后停机。我们假设对所有充分大的 有 ;有限个较短的长度可以单独处理。
我们所用的标准通用模拟事实如下:存在一台确定性通用机器 ,使得对每一台固定的确定性多带机器 ,在长度为 的输入 上模拟 的 步,至多需要 的
步,其中包括对 的有限编码的访问。常数依赖于 ,而不依赖于 或 。对数因子反映了对固定条数纸带的高效模拟;我们直接使用这一标准结果,此处不证明纸带模拟。模拟必须区分接受与拒绝,并持续进行,直到被模拟的机器停机或外部时钟到期。
若存在某台机器在时间 内判定一个语言,而 满足 ,则该语言属于 。这是对所有此类界取并集,而不是单个固定常数倍的时间类。
定理
定理 4.3.1
(带时钟的时间层级定理)
对满足上述增长假设的时间可构造函数 ,存在一个属于 的语言,它不属于 。因此后一个类是 的真子类。
这一陈述是一个保守的版本,明确留出了读入输入所需的余量。它并不声称任意一对仅相差常数倍的界都能给出分离,也没有消除对数量级的模拟代价。
推论 4.3.2
(多项式时间预算的严格分离)
对固定整数 ,确定性多带类满足 。标准的多项式时钟应理解为至多相差无关紧要的常数与低阶时钟约定;这些约定给出同一个 类。该结果分离的是这些类中的语言,而不是为某个熟悉的具体问题指定精确的运行时间。
证明
固定确定性机器的一个有效枚举 。如下设计对角判定机 ,其输入为长度为 的二进制串 。若 具有形式 ,则把其开头的一段解释为索引 ;后缀 是填充,不改变所选中的机器。不含零的输入可以指定一个固定答案。扫描输入,并在 时间内在另一条纸带上写出一个真实的一元串 。在该纸带上运行 时钟,同时用 在整个输入 上模拟 。若模拟在时钟到期之前停机,则输出相反的答案。若时钟先到期,则接受。
把索引解码放进时钟之内
有效枚举未必能随 快速给出第 台机器的描述。因此,统一的模拟过程必须在时钟启动之后,才开始解码或枚举该描述。每一步解码、复制和模拟都计入带时钟的过程。若输入选中了一个极其庞大或不便处理的描述,它可能在机器尚未初始化时就已超时;按约定给出的超时答案,仍然是一个完全有效的判定。
对于一个固定的候选索引 ,解码其有限描述需要固定的有限步数 。矛盾论证可以把这笔开销吸收进该候选机器的模拟常数中。然而,在所有可能的索引与任意输入之上,我们并不需要 的一致上界:实际完成的工作量由外部时钟限定。因此,该证明不会不慎将 的整体运行时间界乘上一个随输入而变、没有上界的描述常数。
时钟和解释器都是固定的多带机器。一台组合机器可以利用分开的纸带区域,以及二者控制状态的有限乘积,轮流给每个部分执行一步。这样的一轮只花费固定的步数;解释器所做的长时间扫描或代码构造则消耗许多轮。只有一元输入带和少量初始标记在计时开始前准备好,耗时 。特别地,我们从不预先写下 个时钟标记,也不假定模拟的纸带读写头移动其实现代价为零。
模拟与时钟轮流进行,所以 的实际时间为 ,其中包括检查输入前缀、写出一元带以及初始化模拟。初始的一元带有 个单元格;没有预先创建任何大小为 的对象。由于时钟会停机,这一确定性计算的每个分支都会停机。在分配的模拟时间内拒绝的机器同样会被翻转为接受;超时不会被误当作被模拟语言的非成员资格的证明。
针对单个固定候选机器利用渐近间隙
证明
(与单个固定候选机器的矛盾)
假设为了导出矛盾,某台确定性机器 在时间 内判定 的语言。对这个固定的 ,通用模拟的界为
确实,由增长假设有 ,并且最终有 ,所以 。对每个充分大的 ,任取一个以 开头、长度为 的输入;填充使得这样的输入在任意大的长度上都存在。在该输入上,模拟在时钟之内完成。于是由 的定义得 ,这与 判定同一语言的假设相矛盾。
对这个固定的索引,索引解码的代价 同样是 ,因此不会改变上述结论。若假想的判定机的运行时间界是 而不是恰好 ,其常数同样可以被吸收:乘以一个固定常数不会破坏小 o 界。输入长度的最终阈值只在选定该候选机器及其常数之后才选取。证明并不需要一个对所有机器索引同时有效的单一阈值。
证明透视
为什么先固定候选机器,再选取长度门槛
唯一不寻常的一步是选择的次序:先固定候选机器 ,然后才选取长度门槛。这个次序使与机器相关的常数 与 得以被吸收:对每个固定的 , 都成立,尽管没有单一的门槛对所有 同时有效。填充是第二项要素:它使索引 成为每个足够大长度的输入的前缀,渐近界因而真正用得上。增长假设 支付读入输入的代价,而 小 o 因子 支付通用模拟的代价。论证以直接的分歧作结:在某个填充后的输入上,模拟在时钟之内完成, 输出与 相反的答案。若没有这个间隙,这一步就会失败。对于 ,模拟代价 对大的 约为 ,只要 就超过时钟,因此时钟可能先到期, 就不一定与 不同。
请注意, 从不需要计算 ,不需要估计竞争机器的渐近复杂度,也不需要识别哪些候选机器满足小 o 条件。它对每个输入都遵循同一条有限的时钟规则。较小的界这一假设只出现在外部的矛盾论证中,在那里它保证所谓更快的判定机最终会及时完成其模拟,从而被矛盾所否定。若让算法去检验这一假设,就会引入一个完全不同且没有依据的可计算性要求。
至于包含关系:每个满足 的函数 最终都是 ,而有限个较小的输入可以被吸收进常数。对角语言属于较大的类,却不属于较小的类,所以该包含关系是真包含。
增长条件只是最终成立的。选取一个固定长度,使其之后条件成立,并在更短的输入上用一张有限表任意定义对角语言。这张表是单个有限机器描述的一部分,即使它的常数规模很大;它并不给出机器在无穷多个长度上的答案。带填充的矛盾论证所用的长度,同时超过这个固定的截止点和所选候选机器的收敛阈值,因此这张表不会产生干扰。
时间可构造性同样是操作意义上的要求。仅仅写出某个设想截止时间的二进制数值,并不能提供本证明所用的时钟。我们假设存在一台真实的机器,它的步骤在所述模型下实现这一截止时间。这个假设使每次超时都是有效的,使每个输入都是可判定的;它并不是要求对角机还要能对作为数据给出的任意函数识别该条件。
证明
(多项式时钟下的比值)
对于多项式推论,取阶为 的时钟。对于阶为 的候选界,相关的比值是 的常数倍,它趋于零。例如,代入 ,收敛性化为 。因此层级语言不在任何 的常数倍之内,而其构造仍然落在 的常数倍之内。普通的包含关系也直接成立,只需允许较小预算的判定机留有未使用的额外时间。
这是语言类之间的严格分离,并不是声称所有阶为 的算法都需要那么多时间。较大类中的许多语言本来就有更快的算法。该构造也没有给出为任意给定程序寻找紧下界的统一方法:它的单一对角语言被刻意设计为,在每个足够快的候选机器的填充输入上与该候选机器不一致。
反例模式
一半的时间并不是更小的类
断言:由于对每个 都有 ,该定理应给出一个属于 而不属于 的语言。这是错误的。按定义, 允许 步,而 ,所以两个类相等。定理的假设在此并不成立:对 与 ,比值 趋向无穷大,而不是趋向零。上述证明需要至少相差一个对数因子的间隙,而不是仅仅数值更小。
例题详解
例题 4.3.3
(多项式时间界)
取 (),在小的 处采用无关紧要的时间可构造约定。该定理给出一个语言,它可在 时间内判定,却不能在 时间内判定:事实上 。这一分离涉及的是所选模型下的确定性时间类,并不意味着某个熟悉的自然问题恰好具有这样的复杂度。
例题 4.3.4
(为什么填充很重要)
设目标机器是 ,由前缀 表示。在每个足够大的长度上都有以该前缀开头的串,例如该前缀后面接上所需数量的零。模拟常数 可能极其巨大,但小 o 的收敛最终会压过任何固定的 。若 只有一个短的编码,我们就无法在任意大的输入长度上援引渐近的运行时间界。
例题 4.3.5
(一个对数因子与两个对数因子)
设在大的长度上 。界 满足 ,所以该定理排除了以此为界的判定机去判定所构造的语言。相反, 的比值为一,不在本陈述的覆盖范围内。它的模拟代价可能仍然是 的一个固定比例,再带上依赖于候选机器的因子,对这个时钟而言就太大了。因此,仅仅在数值上小于 ,并不是这里所证明的假设。在充分大的长度上,取整约定(向下取整或向上取整)都不会改变这两个比较。
常见错误
对角机必须在比较双方答案的同一个完整输入上模拟候选机器。另外,仅仅说“ 小于 ”是不够的:证明必须计入通用模拟器的 因子以及处理输入的代价。最后,该定理给出的是一个专门构造的语言;它既没有证明 ,也没有给出某个具名的 NP 完全问题的无条件下界。
总结
带时钟的模拟使对角化不会无限运行下去。填充提供了任意长的、指名每个固定候选机器的输入,而小 o 的间隙吸收了该机器固定的模拟常数。在所述的可构造性与模拟假设之下,这些要素在确定性时间内部造出了无条件的严格层级。
练习
快速检查
(解释为什么 。)
解答 · 答案
比值为 ,它趋于零。
快速检查
(对 ,利用该定理分离 与 。)
解答 · 答案
由于 ,对角语言属于 ,而不属于 。标准的多项式时钟满足可构造性条件。
快速检查
(当被模拟的机器在时钟到期之前拒绝时, 输出什么?若它在截止时间仍未停机呢?)
解答 · 答案
两种情形下它都接受:第一种情形通过翻转拒绝,第二种情形依据约定的超时规则。这两种情形在证明中扮演不同的逻辑角色。
快速检查
(为什么证明允许通用模拟的常数依赖于 ?)
解答 · 答案
一旦固定了某个候选机器 , 就与输入长度无关。尽管有这个固定常数,小 o 的收敛仍使得在所有充分大的填充输入上,开销小于时钟。
快速检查
(该定理是否证明了 SAT 不能在二次时间内求解?请解释。)
解答 · 答案
不能。所构造的分离语言不必是 SAT,甚至不必属于 NP。该定理给出的是时间类的分离,而不是对较大类中每个具体问题的下界。