动机
预言机图灵(Turing)机可以询问某个固定集合是否包含一个给定字符串,并在一步之内得到回答。预言机是一种数学手段:它让两类机器获得同样的额外信息,从而考察某种证明技术能够推出复杂性类之间的哪些关系。如果一种技术在任意预言机下都原封不动地成立,那么这一类型的单个论证,就不可能确立一个在某个预言机世界中不成立的答案。
我们将构造一个预言机,使得相对于它,确定性多项式时间与非确定性多项式时间不同;并利用一个 PSPACE 完全的预言机得到二者相等的世界。这些构造讨论的是相对化的复杂性类,并不能判定通常意义下的 P 对 NP 问题。
定义
定义 4.4.1
(预言机与相对化的类)
预言机 是一个固定的集合。确定性预言机图灵机可以写下一个查询字符串,并得到一个回答位,指示该字符串是否属于 ;非确定性预言机图灵机还可以分支。时间界包括写下查询的时间,而一次预言机回答只计一步。因此,运行 步的机器不能写出长于 的查询。
用 和 分别表示带有同一预言机 的确定性和非确定性多项式时间机器所判定的语言。按这些定义,并不要求预言机是可计算的,尽管下面的分离构造可以做到可计算。空预言机在相差一个平凡模拟的意义上还原为通常的机器模型。
我们使用真量化布尔(Boolean)公式 TQBF 的多项式空间完全性,该结论来自配套的空间复杂性一章。具体而言,TQBF 属于 PSPACE,并且每个 PSPACE 语言都有到它的确定性多项式时间多一归约。此处不重新证明该完全性定理。
定理
定理 4.4.2
(两种不同的预言机结果)
存在预言机 和 ,使得
前一个分离与后一个相等是关于两个不同的固定预言机的陈述,对未相对化的复杂性类并不构成矛盾。
主要工作是构造 ,同时保证后面的阶段不会改变前面被模拟的机器所观察到的回答。然后我们取 为 TQBF。
构造分离预言机
对预言机 ,定义一元语言
它属于 :在输入 上,非确定性地猜一个 位字符串并向预言机询问一次。对不是一元串的输入则拒绝。见证就是被查询的字符串,写下它需要 时间。
证明
(对每一台带时钟的预言机作对角化)
有效地枚举由一个确定性预言机程序和一个整数 构成的数对。对第 个数对,令 为该程序在长度为 的输入上运行 步后被强制停机的版本,超时视为拒绝。每一台确定性多项式时间预言机图灵机都会以足够宽松的时钟出现在枚举中:增大指数即可吸收它固定的多项式次数和常数。每个 在任何预言机和任何输入上都会停机。
在第 阶段构造有限集合 ,起始为 。同时记住此前各阶段模拟中所有被查询字符串的长度。选取 ,使它大于此前所有选定的长度和所有此前的查询长度,并且足够大,使得
这样的长度是存在的,因为固定的多项式比 增长得慢。用临时预言机 在输入 上模拟 :对已在该有限集合中的字符串回答“是”,对其他所有查询回答“否”。令 为该模拟中被查询的字符串所组成的有限集合。
若 接受,则令 :不加入任何长度为 的字符串。若它拒绝,则选取一个不在 中的 位字符串 ,令 。这样的字符串存在,因为该模拟至多做 次查询。定义最终的预言机为 。
拒绝情形下的加入不会改变模拟中的回答,因为 并未被查询。后面的阶段只在比此前记录的每一个查询长度都更大的长度上加入字符串,所以它们也不可能改变本阶段所见的任何回答。因此, 在 上使用完成后的预言机所作的计算,与被模拟的计算完全相同。此前加入的字符串长度小于 ,之后加入的字符串长度大于 。于是,在接受的情形下,没有任何 位字符串属于 ,故 ;在拒绝的情形下,,故 。两种情形下 在该输入上都判断错误。
每一台确定性多项式时间预言机图灵机都带着适当的时钟出现在枚举中,所以没有一台能判定 。由于 ,这就证明了 。
这些选择可以做到有效:取满足所述界的最小 ,并在需要时取字典序最先的合格 。每个阶段都是有限的,因为被模拟的机器带有时钟,而临时预言机是有限集合。要判定给定字符串是否属于 ,运行各阶段直到选定长度达到或超过该字符串的长度;严格递增保证这一点必然发生,而之后的阶段不可能加入该长度的字符串。因此,这一具体构造可以给出一个可计算的预言机,尽管计算它并不属于多项式时间预言机图灵机模型的一部分。
证明透视
保护查询,而不只是对角线长度
只把后面的对角线长度选得比此前选定的长度更大是不够的:较早的机器可能查询了长得多的字符串。该构造记录每一个查询长度,并把此后所有的加入长度都选在这些长度的最大值之上。在拒绝的情形下,它还在当前长度上选取一个未被查询的字符串。这两重保护使被模拟的查询记录在最终的预言机中保持不变。
例题详解
例题 4.4.3
(一个有限阶段)
设一台被模拟的机器在 上作出少于十六次查询并拒绝。在十六个四位字符串中,至少有一个未被查询。加入这样一个字符串,会使该一元输入属于 ,同时保持机器刚才看到的每一个回答不变。这只是一个有限的示意;真实的阶段还必须使所选长度大于所有此前受保护的查询长度,并满足该阶段特定的时钟不等式。
例题 4.4.4
(为什么较长的查询必须受到保护)
在使用输入长度四的某一阶段,机器可能查询一个十位字符串。如果后面的阶段被允许加入恰好这个十位字符串,那么较早的模拟就可能从回答“否”变为回答“是”,其记录的输出也许不再有效。要求下一次加入的长度大于十,就防止了这种特定的破坏。仅仅保护输入长度四是做不到的。
例题 4.4.5
(未被查询的见证的存在性)
如果某个模拟在长度 上至多作出 次不同的查询,它就不可能检查全部 个七位字符串。因此可以选出一个不在被查询集合中的字符串。证明所用的是所选长度上可能的见证的个数,而不是假定机器的预言机查询相互独立或带有随机性。
反例模式
为何长度必须胜过时钟
声称:对角阶段在任何输入长度上都有效,所以不等式 只是技术细节。取 ,以及查询全部八个三位字符串、并恰在某个回答为是时接受的机器。对 的 种选择,逐一验证可知:它接受 当且仅当 ,所以它在这个长度上对每个预言机都正确,也就没有字符串可以加入来击败它。这台机器只需约 步,这正是各阶段必须选取满足 的 、让至少一个字符串不被查询的原因。
使两个类相等的预言机
定理 4.4.6
(一个 PSPACE 完全的预言机)
令 。则
证明
(通过 TQBF 得到的两个包含关系)
由于 TQBF 在多项式时间多一归约下是 PSPACE 完全的,每个 PSPACE 语言都可以被一台多项式时间机器判定:它先计算该归约,再向 作一次查询。因此 。
反方向则是用多项式空间模拟一台多项式时间的非确定性 预言机图灵机。沿任何一条分支,它只写下多项式多个符号,并作多项式多次查询,每次查询的长度都是多项式。为回答一次查询,运行 TQBF 的确定性 PSPACE 算法,并在之后重复使用其工作区。以深度优先方式遍历非确定性计算树,只要某条分支接受就接受。由多项式多个多项式大小的格局组成的栈,加上一次多项式空间的预言机计算,只使用多项式空间,尽管这一模拟可能耗费指数时间。因此 。
平凡的包含关系 使包含链闭合,从而证明了相等。“预言机”一词在这里是本质的:多项式时间机器被赋予单位代价的 TQBF 成员资格回答;这个证明并没有把 TQBF 放进通常的 P 中。
例题 4.4.7
(把一次 PSPACE 计算化为一次预言机提问)
给定一个 PSPACE 语言 ,令 为它到 TQBF 的多项式时间归约。在输入 上,预言机图灵机计算 ,询问其是否为真,并返回该回答。归约与查询的构造相对于 是多项式的;预言机的回答则由模型提供。这解释了较低一侧的包含关系,而并未宣称存在通常意义下 TQBF 的多项式时间算法。
这两个构造意味着什么
在本文的讨论中,如果一个证明在把所有机器和复杂性类换成相对于任意固定预言机的版本之后依然有效,就称它为可相对化的证明。若某个统一的证明对每个预言机 都确立了 ,它就会与分离预言机矛盾。若它对每个预言机 都确立了 ,它就会与使二者相等的预言机矛盾。因此,一个解决未相对化问题的证明不可能具有这两种普遍可相对化的形式中的任何一种。
这是对一种证明策略的限制,并不是说 P 对 NP 问题独立于通常的公理,也不是说对角化论证毫无用处。证明可以使用在任意预言机访问下不会保持的性质。该定理也并不断言所有预言机都给出同一结果:它的力量来自于展示了两种不同的选择。
常见错误
常见错误
(查询可以比输入更长)
确定性多项式时间机器可以查询比其输入更长的字符串,所以在分离构造中只保护此前的输入长度是不够的。不等式 保证了在所选长度上存在未被查询的字符串;它并不说明机器不能查询更长的字符串。
常见错误
(预言机陈述针对的是固定的预言机)
赋予非确定性机器的是与确定性机器相同的预言机。预言机下的相等或分离并不会自动转移到空预言机的情形。
总结
对角化构造在每个阶段至多加入一个精心选择的预言机字符串,并保护此前所有的查询长度,从而把一个一元见证语言放进 。一个 PSPACE 完全的预言机则给出相反的相等关系。两个世界合在一起说明,为什么对所有预言机统一成立的论证无法解决 P 对 NP 问题。
练习
快速检查
(为什么对每个预言机 , 都属于 ?)
解答 · 答案
在输入 上,猜一个 位见证并查询它。当且仅当预言机回答“是”时接受。
快速检查
(在拒绝的阶段,为什么在所选长度上必定存在未被查询的字符串? 为什么加入这个未被查询的字符串能保持当前的模拟不变?)
解答 · 答案
该长度的字符串有 个,而总查询次数少于 ,所以至少有一个未被查询。 新字符串不在被查询的集合中,所以加入之后,确定性模拟中的每一次查询得到的回答都与原来相同。
快速检查
(为什么后面的加入长度必须大于此前的查询长度,而不只是大于此前的选定输入长度?)
解答 · 答案
机器可以查询比其输入更长的字符串。后面的阶段若在这样的长度上加入字符串,就可能改变较早记录中的某个回答。
快速检查
(如果被模拟的机器在某一阶段接受,在该选定长度上如何选取预言机?)
解答 · 答案
在该选定长度上不加入任何字符串。此前和此后的加入具有不同的长度,所以最终的预言机在该长度上没有任何字符串。
快速检查
(为什么 TQBF 的完全性蕴含 ? 为什么 ?)
解答 · 答案
计算到 TQBF 的多项式时间归约,并作一次预言机查询。模型在一步之内提供回答。 以深度优先方式遍历多项式时间非确定性计算树,并用可重复使用的多项式空间算法回答每一次多项式长度的 TQBF 查询。
快速检查
(分离预言机是否证明了通常的 ? 两种预言机结果的存在是否说明 P 对 NP 问题独立于标准公理?)
解答 · 答案
不。只有当两个类都配备了所构造的预言机时,它才证明分离。 不。它限制的是相对于每个预言机都依然有效的证明论证;它并不是关于通常问题的形式独立性定理。
快速检查
(为什么可以枚举带时钟的程序与多项式指数的数对?)
解答 · 答案
每台多项式时间预言机图灵机都有某个多项式时间界。一个足够大的固定指数给出的时钟可以超过该界,而每个程序与指数的数对都可以被枚举。
快速检查
(在选取之后所有的长度之前,一个阶段必须保存什么信息?)
解答 · 答案
它必须记录当前模拟中用到的所有查询长度,以及此前受保护的长度,使得未来的加入避开所有此前被查询的字符串。