动机
Savitch 定理告诉我们如何用确定性空间模拟非确定性空间,但并没有说明:给确定性机器更多的存储,是否会使其能力更强。在一个可构造性假设之下,空间层级定理回答了这一问题。其对角化机器在一个精心选取的中间存储预算内模拟某个候选机器,等待足够长的时间以检测重复出现的格局,然后与该候选机器的输出相反。
关键的比较是渐近意义上的。一个程序具有固定的描述和固定的模拟常数,而两个空间界之间的比值可以无限增长。格局的编码与计数至关重要:若模拟过程要等待任意一台机器停机,则该模拟本身就不是一个判定器。
定义 3.7.1
(空间界与空间可构造性)
我们使用带有只读输入带和有界工作带的确定性机器。工作空间界计算的是被访问过的工作单元数,而不包括只读输入。函数 在此称为空间可构造的,是指存在一台确定性机器,对于长度为 的输入,能够在 空间内构造并恰好标记 个工作单元。我们假设对于充分大的 有 ,从而机器能够存储输入头位置和基本计数器。改变一个界的有限多个取值,不会影响所得的渐近空间类。
为什么空间界可以充当时钟
定理 3.7.2
(格局数界)
固定一台具有有限工作字母表的确定性机器 。在长度为 的输入上,若 至多使用 个工作单元,则其可能的格局数至多为 ,其中 是依赖于 、而不依赖于 或 的常数。若某次计算出现了重复格局,则该计算此后永远不会停机。
证明
(计算格局数与鸽巢步骤)
一个格局记录有限控制状态、已访问工作窗口的内容、工作头位置以及输入头位置。大小为 的工作字母表至多给出 种可能的窗口内容;各个头位置分别至多贡献因子 与 ,而状态集是固定的。对于适当的 ,乘积至多为所示的 2 的幂,通过增大 也可以涵盖 很小的情形。
确定性的下一步规则使相同的格局产生相同的后继。若某个格局在停机之前重复出现,则其两次出现之间的片段将永远重复,因此该计算此后不可能停机。所以,只要对格局数有一个有效的界,模拟在超过该界的步数之后便可安全地宣告不停机。
例题 3.7.3
(一个小的有限状态空间)
设某机器有两个控制状态,工作带为二进制且限制在三个单元内,有四个可能的工作头位置和六个输入头位置。则至多有 个可能的格局。若一次确定性计算在观察了 385 个格局之后仍未停机,则其中必有重复。这个有限的例子说明了鸽巢论证;层级定理的证明需要的是输入长度增长时的一般界,并且在整个模拟过程中对机器描述作一致的处理。
常见错误
(大的时钟并不需要大的带)
一个计数到 的计数器只使用 个比特,尽管数到该值可能需要指数时间。层级论证是一个空间证明,而不是多项式时间的模拟。其巨大的时钟与所声称的存储界是相容的。
概念视角结构
格局构成每点只有一个出口的图
把确定性机器在固定输入上的格局当作顶点,每个格局指向它的后继格局。每个顶点至多有一条出边,而一次计算就是从起始顶点出发的路径。路径恰在到达停机顶点时停机;若重访某个顶点,就是落入环中,永远不会停机。因此时钟只需数到顶点的总数。
模拟一台被描述的机器
我们使用一个针对固定有限机器编码的标准通用解释器。其转移表从只读输入中读取,而不是整体复制到工作带上。对于一台固定的被描述机器 ,模拟其 个工作单元至多需要 个解释器工作单元,其中 是依赖于 及其字母表的常数。解释器可以跟踪被描述机器的状态和头位置,在需要转移时扫描其描述,并对被模拟的工作单元计数。额外的扫描可能耗费时间;这里不对时间作任何界的声明。通常的有限字母表编码和通用模拟在此作为背景假设。
对于对角化构造,我们还需要解释器自身的一个一致的格局时钟。我们将被编码的机器描述限制在至多 个输入比特,并将解释器的工作窗口限制为至多 个单元。解释器是一台固定的机器,因此对某个固定常数 ,其自身的格局至多有 种可能。描述已经是固定输入的一部分,不是其格局中另一个变化的分量。该时钟具有 个比特。
例题 3.7.4
(固定程序,增长的填充)
一个编码可以由 的自定界描述后接若干个零构成。对每个固定的 ,其描述长度是常数。通过充分填充,该长度可以变得至多为 ,而被模拟的输入仍是整个填充后的字符串。因此,限制描述长度并不会把任何固定的候选机器从所有充分长的对角化输入中排除出去。
在两个界之间选取预算
设 为空间可构造函数,最终不小于 ,且 。定义
则 且 。取上整不改变这两个极限。特别地,最终有 。对角化机器可以在 工作空间内计算出一个足够精确的整数 :构造两个界,以二进制表示它们的数值,相乘并取整数平方根。由于 ,对于充分大的 ,这一界已包含构造 所需的工作量。对于有限多个较短的输入,机器可以采用任意固定的后备行为。
定理 3.7.5
(确定性空间层级定理)
在上述假设下,
证明
(对每台固定的小空间机器作对角化)
对于长度为 的输入 ,对角化机器首先尝试解析一个长度至多为 的有效自定界确定性机器描述。若输入中不存在这样的描述,则拒绝。否则,它计算 ,分配一个含 个单元的解释器工作窗口,并在同一个完整输入 上模拟被描述的机器 。若解释器试图离开其窗口,则对角化机器拒绝。它同时维护上文所述的一致格局时钟。若时钟在模拟停机之前到期,则拒绝。若被模拟的机器接受,则对角化机器拒绝;若其拒绝,则对角化机器接受。
该构造总会停机:窗口越界、被模拟机器停机或有限时钟,三者之一会终止运行。构造 的代价为 空间;模拟及其时钟的代价为 空间。因此所得语言 属于 。
假设为导出矛盾,存在一台固定的判定器 ,对所有充分大的 ,使用至多 个工作单元判定 。取编码 的填充输入 ,其长度趋于无穷。最终满足描述长度的限制。对于这个固定的 ,通用解释器所用的空间至多为 ;由于 且 ,对所有充分大的此类长度,该值小于 。因此窗口不会溢出。被模拟的判定器会停机,并且时钟足够长:否则,有界确定性解释器的某个格局会重复,模拟此后便永远无法停机。于是对角化机器输出与 相反的结果,与 判定 的假设矛盾。故 。
由于最终有 ,普通的包含关系成立。严格性的证明在吸收其模拟常数时需要的是单个固定的候选机器;它并不假设同一个常数对每个被编码的程序都同样适用。
证明透视
各项假设在对角化论证中的位置
这个论证分成两半,量词并不相同。上界对每个输入都成立:机器停机并使用 空间,这需要可构造性(用来建立 )、(使 ),以及由同一台固定解释器、同一个常数 给出的统一时钟。下界只涉及单个候选机器 ,其常数 在 增大之前已经固定。不显然的一步是填充:对角化机器从输入中读取 的描述,补上零使固定的 出现在无穷多个输入上,所以描述长度的上限不会排除任何候选机器。假设 在下界中恰好用一次,即 ,使窗口最终超过 。若 ,这一步就失效: 只约为 ,窗口可能溢出,对角化机器便在没有与 作出相反判定的情况下拒绝,不会产生矛盾。
例题 3.7.6
(对数空间与对数平方空间)
取 与 。二者均为空间可构造的,且 。该定理给出一个可在 空间内判定、但不能在 空间内判定的语言。证明是借助对角化判定器的存在性证明;它并未指出具有此性质的某个熟知的完全问题。
反例模式
常数倍数永远不能分离空间类
一个诱人的说法是:当 时,层级定理仍给出 ,因为较大的界允许十倍的存储。取 及 。此时 并不趋于零,假设不成立,结论也不成立。若机器 以至多 个工作单元判定某语言,便构造 :其工作字母表由 的十个符号组成的区块构成,区块内的位置由有限控制记住。于是 逐步模拟 ,至多使用 个区块单元,并判定同一个语言。因此即使对精确的界,也有 ;严格分离需要小 o 的差距 。
一个推论及对时钟的进一步考察
推论 3.7.7
(PSPACE 内部的一个严格包含)
。
证明
(对数平方空间的见证语言)
对数平方的例子给出一个属于 但不属于 的语言。由于 以 的某个多项式为上界,该语言属于 PSPACE。每台对数空间机器也只使用多项式空间,因此 ;所构造的语言使这一包含关系成为严格的。这一结论使用的是确定性空间层级定理,并不能解决 P 与 PSPACE 之间的关系。
例题 3.7.8
(指数时钟所用的空间)
设有界解释器至多有 个可能的格局。从零数到 需要 101 个二进制比特,外加常数量的控制空间。这样大小的计数器可以与解释器窗口并行维护;在空间类论证中,允许其运行时间可能极其巨大。若对某个判定器的模拟始终保持在其窗口之内,则它必定在格局重复之前停机,因此该时钟不会错误地使其超时。
该时钟所界定的是有界解释器的格局,而不仅仅是带有依赖于程序的字母表的被模拟机器的格局。这一选择在对角化构造中产生了唯一的一致常数。反过来,为了说明任何固定的小空间候选机器都能放入解释器窗口,证明可以使用依赖于该唯一候选机器的常数。若混淆这两个量词,对角化判定器将失去一致的界。
该定理比较了什么、没有比较什么
该定理讨论的是确定性空间类与语言。它既没有说较大类中的每个语言对较小类都是困难的,也没有证明诸如 P 对 PSPACE 之类的分离。它只产生差集中的一个语言。它同样没有建立非确定性空间层级定理,后者需要另外的论证。
空间可构造性并非装饰:对角化机器必须分配并监控一个由所指定函数导出的预算。如果无法有效地获得这些界,上述构造便得不到论证。假设 用以支付对只读输入的索引以及模拟器计数器所需的空间;亚对数模型则需要额外的谨慎处理。
具有相同间距的非确定性层级成立,但对角化机器现在必须取答案的补。
自然的下一个问题
同样的间距能分离非确定性空间吗?
具有相同间距的非确定性层级成立,但对角化机器现在必须取答案的补。
具有相同小 o 间距的非确定性空间层级同样成立。上面确定性的证明把被模拟机器的答案反转,而对非确定性机器来说,这等于要在可用空间内判定其语言的补集。因此非确定性的情形需要另一个论证,非确定性空间的补集结果就是相关的工具。
练习与解答
快速检查
(为什么指数长度的时钟可以放入关于其指数的线性空间中?)
数一数时钟所达到的最大数需要多少比特。
解答 · 答案
计数到 的二进制计数器只需要 个比特,尽管它可能执行指数次递增。
快速检查
(若确定性格局在机器停机之前重复出现,会出现什么问题?)
比较每次出现之后的后续计算。
解答 · 答案
确定性使得相同的未来重复出现,因此机器将永远循环,此后无法停机。
快速检查
(为什么对角化机器是在整个填充后的输入上,而不是仅在其描述上,模拟被描述的程序?)
候选机器必须判定哪一个输入?
解答 · 答案
所谓的候选机器在完整输入上判定对角化语言。正是在同一输入上的不一致产生了矛盾。
快速检查
(为什么 最终大于 的每个固定倍数?)
用一个平方根给 一个下界。
解答 · 答案
由于 且 ,该比值趋于无穷。
快速检查
(空间可构造性假设用在何处?)
想一想对角化机器在模拟之前须先计算什么。
解答 · 答案
它使对角化算法能够在较大的空间容许量之内,构造并监控其依赖于输入长度的存储预算。
快速检查
(该证明是否蕴含 严格小于 ?)
检查常数倍数是否满足小 o 假设。
解答 · 答案
不蕴含。常数倍数不满足所需的小 o 关系,而上述区块打包的论证表明这两个类相等。
快速检查
(该定理是否证明了 P 不等于 PSPACE?)
它到底分离了什么?
解答 · 答案
不能。该定理分离的是适当的确定性空间界;它并未比较所有多项式时间语言与 PSPACE。
快速检查
(即使层级定理的证明没有指出差集中某个熟知的自然语言,为什么仍能得出 ?)
见证语言是否必须是标准问题?
解答 · 答案
它构造了一个属于 而不属于 的特定对角化语言。较大的类包含于 PSPACE,因此即使我们不能把该构造出的语言认作某个标准的图问题,它也见证了严格性。