动机
一个有界误差的随机算法必须在接受概率与拒绝概率之间保持一个可见的间隔。如果接受概率仅仅比二分之一大一个无穷小的量,但这一差值的符号被保证是正确的,又会怎样?类 PP 研究的正是这种情形。对接受路径进行计数可以使这一定义精确化,并说明为什么普通的抽样无法自动地在多项式时间内判定如此微小的差值。
本单元中的所有概率均针对固定的输入 。多项式时间随机机器使用相互独立的均匀比特。通过用未使用的比特进行填充,我们可以假定:对每个长度为 的输入,机器恰好读取 个随机比特,其中 是一个取整数值的固定多项式。每个随机串的概率为 ,即使有多个随机串导致完全相同的计算历史也是如此。在概率计算中,对随机串计数而不是对不同的计算历史计数,这一点至关重要。
严格多数与路径计数
若存在多项式时间随机机器 ,使得
则称语言 属于 。严格不等号是定义的一部分。在否定实例上,接受概率可以恰好等于 。机器不需要与 之间存在任何逆多项式量级的间隔;使用 个随机比特时,接受概率的最小正变化量可以是 。
对固定的输入,令
则 。PP 条件等价于 ;当 时,应直接按概率不等式来理解。整数 统计的是接受的随机串,其中也包括机器经过填充但并未检查的随机串。
例题 5.2.1
(在此约定下,平局属于否定实例)
设某机器使用三个随机比特。若它在八个随机串中的五个上接受,则其接受概率为 。若它在四个上接受,则概率恰为 ,因此严格多数谓词给出否定的回答。若它在三个上接受,回答同样是否定的。若把约定从 改为 而不处理平局,则该机器所识别的语言可能发生改变。
常见错误
(多数不一定是稳健的多数)
接受概率为 时,它确实大于 ,但优势可能是指数级小的。基于常数间隔和多项式个独立样本的 BPP 式证明不能被简单地照搬。PP 只是规定了精确概率位于阈值的哪一侧;它并不断言存在一个高效的实验能够估计这一符号。
见证计数与阈值谓词
若存在多项式 和确定性多项式时间谓词 ,使得
则称函数 在见证形式下属于 。较短长度的消息可以借助无歧义的长度约定编码为定长串。见证计数是一个非负整数,而不是一个判定比特。把非确定型机器的分支规范化为这种见证形式是标准的背景等价结论;我们直接使用上面给出的形式。
命题 5.2.2
(PP 作为见证计数上的阈值)
语言 属于 PP,当且仅当存在由 个见证比特表示的 函数 ,以及一个多项式时间可计算的填充约定,使得
证明
(证明)
给定一台使用 个随机比特的 PP 机器,令 以 作为随机串来模拟该机器。若 可能为零,则追加一个未使用的随机比特。追加操作使随机串的总数与接受的随机串数都加倍,因而保持该比例是否严格大于二分之一不变。由此得到的计数属于 ,并满足上面给出的阈值条件。
反之,给定上述见证谓词,从 中均匀地抽取 ,并当且仅当 时接受。接受概率为 ,它恰好在 上大于二分之一。抽样与验证都只需多项式时间。填充约定对每个输入长度统一地固定长度;它不会改变严格阈值。
例题 5.2.3
(在已声明的变量列表上对赋值计数)
对于 ,四个赋值中有三个满足该公式。因此,均匀抽取一个赋值时,接受概率为 ,大于二分之一。对于 ,恰有两个赋值满足它,形成平局。已声明的变量列表是重要的:添加一个未使用的变量会使计数与赋值总数同时加倍,比例保持不变。添加变量与在保持分母不变的情况下仅仅改变所声称的计数并不是同一种操作。
例题 5.2.4
(相差一个接受串的间隔)
设 。一台在 个随机串中的 个上接受的机器,其概率为 。另一台在 个串上接受的机器则恰好是平局。当 随输入长度以多项式速度增长时,相差一个串会产生指数级小的概率间隔。原则上,精确计数能立即区分这两种情形,而一个小规模的经验样本却很容易使两者看起来相同。
NP 与有界误差随机计算
定理 5.2.5
(NP 与 BPP 包含于 PP)
且 。
证明
(证明)
对于 BPP,使用一个有界误差的判定器,它在肯定实例上的接受概率至少为 ,在否定实例上至多为 。这些概率位于 的正确一侧,因此同一台机器就是一台 PP 机器。
对于 NP,令 验证长度为 的见证。独立地抽取一个公平比特 和一个均匀的 位串 。若 ,则立即接受。若 ,则当且仅当 时接受。当不存在见证时,接受概率恰好为 。当至少存在一个见证时,第二个分支贡献一个正的量,因此接受概率严格大于 。即使在指数多个候选见证中只有一个有效,该构造仍然是多项式时间的。因此,严格阈值能够正确地区分这两种情形。
例题 5.2.6
(一个见证即可使精确多数发生倾斜)
设有八个候选见证,且恰好有一个通过验证者。在由 NP 到 PP 的构造中,立即接受的分支贡献八个接受的数对 ,验证分支再贡献一个,因此十六个串中有九个接受。若没有见证,则十六个串中恰有八个接受,形成平局。该构造并不定位见证;它把见证的存在性编码在一个微小概率差的符号之中。
这两个包含关系都不能证明 PP 具有高效的有界误差算法。NP 的构造可能具有指数级小的优势,而 BPP 的包含只是单向的。这些类之间已知的或被猜想的分离需要额外的论证;此处不作任何断言。
严格多数的补运算
对 PP 机器的输出取反并不足以得到其语言的补,原因就在平局。
反例模式
对调输出得不到 PP 语言的补
假设有人声称,对调 PP 机器 的接受与拒绝输出,便得到识别 的补的机器。取一个输入 , 在其上使用一个随机比特 ,并恰在 时接受。它在 个随机串中的 个上接受,概率恰为 ,故 。对调后的机器恰在 时接受,同样是 个串中的 个,按严格多数规则它也拒绝 。因此 既不在 中,也不在对调后机器的语言中,后者便不是 的补。修补办法是把平局移到接受的一侧,下面的构造正是这样做的。
下面的填充构造在不假设任何间隔的情况下解决了这一边界问题。
定理 5.2.7
(PP 在补运算下封闭)
若 ,则其补集也属于 PP。
证明
(证明)
对原 PP 机器进行填充,使其使用 个随机比特。记 ,并令 为其在 上接受的随机串的个数。添加两个独立的随机比特 ,并重用 位串 。按以下四种情形定义新机器:
- 若 为 或 ,则当且仅当原机器在 上拒绝时接受。
- 若 ,则总是接受。
- 若 ,则当且仅当 时接受。
总共有 个等可能的串。前两种情形贡献 个接受串,第三种贡献 个,最后一种贡献一个。因此新机器在 个串上接受。其严格多数条件为
由于 为偶数而 为整数,该不等式恰好在 时成立。这恰恰是原机器的接受概率不严格大于二分之一的条件。所有额外的检验与模拟都只需多项式时间,因此新机器在 PP 中识别了该补语言。
证明透视
多出来的那一个接受串起什么作用
原计数 每改变一,新计数 就改变二。项 与 把阈值恰好定在 :新计数等于 (即平局),当且仅当 。最后一种情形再加一个接受串;一小于步长二,所以它只在平局 时改变结果,把平局变为接受,而使其他每个非平局的 仍处于原来的一侧。填充到 使 为偶数,因此平局值 是整数,确实可能出现。若没有这个额外的串,构造就会重现简单对调的失败;若额外加三个或以上的接受串,则 (原机器的肯定实例)也会被接受。
例题 5.2.8
(检验边界情形)
取 且原计数 。补运算构造在 个串中有 个接受串,因此其接受的比例严格超过一半。若 ,则新的计数为 个中的 个,按 PP 的约定它拒绝。多出的那个接受串解决了平局;而简单地把原来的每个回答取反,在第一种情形中仍然只有八个串中的 个接受。
概念视角代数
PP 是带符号和的正负号
对每个随机串 ,若 接受就赋值 ,拒绝就赋值 ,并令 。于是 当且仅当 ,所以 PP 问的是一个整数和的正负号,平局即 。在这个形式下,补集构造就是恒等式 :由于 为偶数, 当且仅当 。
由补运算封闭性与 NP 的包含关系可知,同样有 。补运算封闭性证明了 ,但并未证明 ,后者仍是一个独立的问题。
确定性空间上界
精确计数可能需要指数时间,却仍只使用多项式空间。按字典序枚举每一个可能的随机串,在该串上模拟多项式时间机器,并用一个二进制计数器记录接受串的个数。枚举下标需要 位,计数最多需要 位。由于一次模拟只需多项式时间,它也只使用多项式空间,并且其工作空间会在下一个随机串上被重复使用。
命题 5.2.9
(PP 包含于多项式空间)
。
证明
(证明)
对输入 ,计算公共的随机串长度 ,并用一个 位计数器枚举全部 个串。在每个串上分别模拟该 PP 机器,并在它接受时使一个 位的接受计数器加一。最后将计数与 比较,或者将计数的两倍与 比较,以统一处理 的情形。工作带存储这两个计数器以及一次多项式空间的模拟,它们都是 的多项式。该算法在指数多次模拟之后终止,因此它在多项式空间内判定该语言;由这一枚举并不能推出任何多项式时间的界。
例题 5.2.10
(计数器可以很短,而枚举却很长)
当 个随机比特时,共有 个串。下标需要 位,接受计数器需要 位,尽管机器可能需要执行一百多万次模拟。当 时,同样的计数器长度仍是多项式的,而被模拟的串的个数却是 。空间可以重复使用;时间则会不断累积。
计数观点能证明什么,不能证明什么
矩阵的积和式、它在指定归约概念下的 -完全性,以及将多项式层级与计数联系起来的 Toda 定理,都是更进一步的重要结果。此处并不证明它们。完全性陈述必须指明所用的归约和输入编码;涉及计数函数的预言机陈述同样必须指明计数如何返回以及如何计费。上面给出的简单阈值刻画不应被误认为是对这些更深结果中任何一个的证明。
与上文类似, 的计数值可以通过在多项式空间内枚举全部见证来计算,但其结果可能有指数多个可能取值,需要一个合适的输出约定。反过来,仅仅知道计数是否非零是一个 NP 式的判定问题,通常揭示的信息少于精确计数。即使使用同一个验证者,对见证计数、判定存在性以及与一半作比较仍是三个不同的任务。
练习与解答
快速检查
(一台机器使用四个随机比特,并在八个串上接受。它在此输入上是否满足严格的 PP 阈值?)
把接受概率与 比较。
解答 · 答案
不满足。共有十六个串,接受概率为 ;定义要求严格不等式。
快速检查
(在由 NP 到 PP 的构造中,当没有见证时,接受概率是多少?如果至少存在一个见证,情况有何变化?)
分开考虑构造的两个分支。
解答 · 答案
没有见证时恰为 。至少有一个见证时,验证分支会增加一个正的概率,使概率严格大于 。
快速检查
(若某台 PP 机器使用 个比特,并在 个串上接受,则补运算构造在多少个串上接受?)
利用计数 ,其中 。
解答 · 答案
这里 ,因此计数为 ,总数为 。由于 ,原语言处于否定一侧,而其补语言处于肯定一侧。
快速检查
(为什么对机器的输出取反无法处理平局?)
平局在取反之后是什么样子?
解答 · 答案
如果原机器恰好在一半的串上接受,那么取反后的输出同样恰好在一半的串上接受。在严格多数的定义下,两者都是否定。
快速检查
(对全部 个随机串建立下标并对接受的串计数,需要多少空间?)
分别计算下标与计数器的位数。
解答 · 答案
下标需要 位,计数最多需要 位;对每个串都重复使用同一个多项式空间的模拟。
快速检查
(PP 包含于 PSPACE 是否蕴含存在多项式时间的模拟?)
比较顺序执行的步数与所用空间。
解答 · 答案
不能。该构造可能需要枚举指数多个随机串。多项式空间只限制同时存储的量,而不限制顺序执行的步数。