传统的验证者可以读取整个证书。概率可检验证明(probabilistically checkable proof)可以比被检查的部分长得多:验证者使用少量随机比特选取少数几个位置,然后判断所看到的比特是否局部一致。值得注意之处不在于真命题存在证明,而在于:对于假命题,每一个所谓的证明都会以不可忽略的概率未能通过某个随机选取的检验。这一区别把验证误差转化为优化间隙。
局部访问与全局正确性
定义 10.1.1
(概率可检验证明验证者)
概率可检验证明验证者是一个具有随机访问二进制证明串能力的随机化多项式时间机器。对长度为 的输入,其随机性预算限制它所使用的公平随机比特的数目,其查询预算限制它所读取的证明位置的数目。除非明确声明采用非自适应约定,后续查询所选取的位置可以依赖于先前的回答。完备性(completeness)指每个 yes 实例都有一个以指定的高概率被接受的证明;可靠性(soundness)指 no 实例的每个证明被接受的概率至多为指定的较低概率。
证明是在随机硬币被选取之前就固定下来的。它可以依赖于输入,但不能在得知哪些位置被查询之后再选择新的取值。否则,验证者所面对的就是一个自适应的证明者,而不是在检查一个固定的证明。在可靠性条件中,并不假定证明是诚实的。一个正确的论证必须对每一个可能的证明串(包括那些并不编码任何有意义赋值的证明串)都给出接受概率的界。
对于 个随机比特与 次查询,记号 表示在固定的完备性与可靠性常数下对应的验证者类,通常取完美完备性且可靠性至多为 。验证者的运行时间是多项式的,地址具有多项式长度。当使用 个随机比特时,可能的随机串只有多项式多个;若查询次数为常数,则每个随机串只选取常数个位置。随机访问是一个明确的资源约定:移动物理纸带头到远处位置,并不按验证者拥有顺序纸带那样来计费。
命题 10.1.2
(消除常数次查询的自适应性)
设 是对每个输入和随机串至多进行 次二进制查询的验证者。则存在一个非自适应验证者 ,使用相同的随机比特及至多 次查询,并且对每个固定证明的接受概率与 完全相同。若 为常数,则 也为常数。
证明
(展开查询树)
固定输入和验证者的随机串。若它至多进行 次二进制查询,可能的查询与答案历史构成一棵至多有 个查询节点的二叉树。非自适应验证者可以计算这棵树中出现的所有位置,一次读取这些位置,再用答案模拟原来的路径。重复位置都从同一个固定证明中一致地读取。构造这棵树只用验证者的代码、输入及其固定随机串,不依赖某个候选证明。模拟时舍弃与实际读到的答案不一致的分支。当 是常数时,新的查询上界仍是常数,且对每个固定证明的接受概率不变。
证明透视
查询树由什么构成
论证的关键在于这棵树由什么构成。它只用验证者的代码、输入和固定的随机串,所以对每个证明都是同一棵树;因此可以在读取任何证明比特之前就写下全部位置,也因此对每个固定证明分别保持接受概率不变。舍弃与答案矛盾的分支,是使模拟忠实的步骤,因为真正的路径只有一条。代价是树的大小: 为常数时 也是常数,所以容许自适应不会改变常数查询类;但它随 指数增长,所以同一转换未必能保持随输入增长的查询预算。
为什么仅靠抽样是不够的
在这个抽样实验中,取 个布尔(Boolean)约束,其中 是整数。均匀选择一个约束恰好使用 个公平比特;任意 的精确均匀抽样则需要额外的实现论证。考虑对这些约束提出的一个赋值。验证者可以均匀地选取一个约束,读取其中的变量,若该约束被满足则接受。若赋值满足每个约束,则必然接受。若它违反了比例为 的约束,则拒绝概率恰为 。仅当每个候选赋值都至少违反固定的正比例的约束时,这一检验才具有至多为 的可靠性。
概念视角组合
把非自适应验证者看成一族约束
设检验是非自适应的,并使用 个随机比特。每个随机串 便指定至多 个证明位置和作用在它们上的一个谓词,即一个约束 。对固定的证明 ,接受概率恰好是 所满足的约束占全部 个约束的比例。可靠性说明:当实例为假时,没有证明能满足超过某个固定比例的约束,这就是关于约束的间隙陈述。
例题 10.1.3
(一个被违反的子句可能很难被察觉)
对整数 取 ,取一对矛盾的单文字子句 与 ,再添加 个恒真子句 的副本。该公式是不可满足的。然而, 的任一取值恰好满足两个矛盾子句之一以及所有填充子句,因此均匀随机的子句检验只以概率 拒绝。随着 增大,该概率趋于零。仅有不可满足性并不能提供一个常数的可靠性间隙。
例题 10.1.4
(一个具有真正间隙的小公式)
考虑四个子句 、、 与 。对 的四个赋值中,每一个恰好违反其中一个子句,所以该公式不可满足,并且每个赋值的值都是 。无论所提供的赋值是什么,均匀选取的子句以概率 被违反。若对同一个固定赋值进行三次独立选取的检验,并要求三次都通过,则接受概率为 。这个例子具有常数间隙,但它并没有说明如何把每个不可满足的公式转化为具有常数间隙的公式;那才是困难的一般构造。
PCP 构造改变了证明的表示方式与检验方式,使得一个假命题不可能被做成与所有局部检验几乎一致。一个证明比特可以描述冗余的编码信息,而不是某一个原始变量。其挑战在于仅用局部视图来强制全局一致性;仅仅对任意证书附加随机抽样并不能解决这一挑战。
作为所陈述依赖项的 PCP 定理
定理 10.1.5
(PCP 定理,标准形式)
在上述随机访问与多项式时间约定下,,其中具有完美完备性且可靠性至多为 。
我们不加证明地陈述该定理中困难的一个方向。它构造了一种局部可检验的编码以及具有所承诺间隙的检验。反向包含关系有一个有用的初等解释:多项式时间验证者只读取多项式长度的地址,所以当只有多项式多个随机串且查询次数为常数时,证明可以由其相关的多项式多个被查询比特来表示。NP 机器猜测这些比特并检查所有随机串,恰当接受比例达到验证者的完备性阈值时才接受。完全形式化的版本必须通过包含沿可能的查询—回答路径所到达的每个位置来处理自适应查询;常数的查询界使得每个随机串只有常数条这样的路径。该定理本身远比这一计数观察深刻。
常见错误
(把定理误读为恢复证明)
该定理并不是断言验证者可以从少数比特恢复整个证明。随机性使得不诚实的证明很可能未通过某次检验;接受是关于所声称实例正确性的一个概率性保证。某一次特定的随机检验可能接受一个假实例,而可靠性的界允许这种情形发生。
从间隙到近似问题
定义 10.1.6
(3-CNF 公式的值与最优值)
对于具有 个子句的 3-CNF 公式,每个子句至多含三个文字(较短子句可用重复文字填充),将一个赋值的值定义为它所满足的子句的比例,并令 为最大的这样的比例。最大值是对所有变量的赋值取的,而一个具体赋值的值可以在多项式时间内计算。可满足的公式其最优值为 ;不可满足的公式其最优值可能接近 ,正如填充的例子所示。
我们不加证明地使用 PCP 困难性的如下间隙形式。
定理 10.1.7
(PCP 困难性的间隙形式)
存在固定的有理常数 以及一个多项式时间归约,把每个 3-CNF 公式 映为一个 3-CNF 公式 ,使得:若 可满足,则 可满足;若 不可满足,则每个赋值至多满足 中 比例的子句。
任何正间隙都可减弱为这样的有理间隙,使阈值成为可计算常数。这是一个额外的非平凡定理,而不是仅仅对原始子句进行抽样的推论。该构造及其与 PCP 定理的关系不在本单元的范围之内。
命题 10.1.8
(间隙排除了多项式近似方案)
假设所陈述的间隙定理成立且 。那么,对于最大化 3-CNF 公式被满足子句比例的问题,不存在多项式时间近似方案。这里,一个方案必须对每个固定的 ,在多项式时间内返回一个实际的赋值,其满足的比例至少为 。
证明
(通过区分两种情形的证明)
假设存在这样的方案。固定常数 ,并使用其对这个值的多项式时间算法。给定一个 3-SAT 公式,构造间隙归约的输出 并运行该近似算法。计算所返回赋值的被满足子句的比例。
若原公式可满足,则 ,所以返回的赋值其值至少为 。若原公式不可满足,则每个赋值(包括返回的那个)的值至多为 。由于 ,将该值与严格介于两者之间的阈值比较,即可在多项式时间内判定 3-SAT。由 3-SAT 的 NP 完全性(此处不加证明地使用),这将推出 ,与假设矛盾。
该定理并不断言 MAX-3SAT 没有有用的近似算法。它排除的是一族在所述假设下可以任意接近最优值的算法。它也没有说每一个单独的 3-CNF 实例都是困难的:该归约确立的是针对必须处理所有实例的一致算法的最坏情形障碍。
例题 10.1.9
(一个数值间隙判定)
仅为说明起见,假设某个归约的间隙为 。以 运行一个方案,在 yes 输出上将产生至少为 的值,而在 no 输出上每个赋值的值至多为 。阈值 可区分这两种情形。这个数值例子说明了证明过程;它并不声称所引用定理的常数恰好是 。
常见错误
(接近最优的值并不是精确答案)
对于任意不可满足的公式,近似算法可能输出一个极其接近 的值;而可满足的公式也可能因为算法是近似的而得到低于 的值。上述判定过程之所以有效,是因为归约产生了一个固定的间隙,并且因为所返回赋值的值可以被检查,而不是因为近似自动地判定了可满足性。
随机性、放大与固定证明
若验证者独立地重复一个常数查询的检验,并在任一检验拒绝时拒绝,则在单次运行中以至多 的概率被接受的假证明,在 次独立运行后被接受的概率至多为 。完美完备性仍保持完美。查询次数增加到原来的 倍,随机比特数也同样增加;对于固定的 ,PCP 定理中的两个渐近界仍然是 与 。这一计算分别适用于每个固定的证明。它并不允许证明在观察到验证者的硬币之后再改变。
例题 10.1.10
(重复一次局部一致性检验)
假设假实例的每个证明通过一次检验的概率至多为 。三次独立的检验只有当三次全部通过时才接受该证明,其概率至多为 。一个被每次检验都接受的正确证明仍以概率 被接受。
下面的例子说明,各次重复必须相互独立。
反例模式
重用同一个随机串不算放大
断言:用同一个随机串把检验重复三次,假证明的接受概率就从 降到 。取一个只用一个随机比特 的验证者,以及假实例的一个固定证明 ,它在 时通过检验、在 时失败,所以恰以概率 被接受。若三次重复都用同一个 ,它们恰在 时一起通过,接受概率仍是 ,而不是 。断言不成立,因为各次重复完全相关。修正:每次重复都抽取新的随机比特,共三个;三次检验便相互独立,全部通过的概率为 。
练习与解答
快速检查
(在上述填充的矛盾公式中,计算被满足子句比例的最优值。)
数一数一个赋值至多能满足多少个子句。
解答 · 答案
每个赋值都违反两个矛盾子句之一,而满足另一个以及所有 个恒真子句。因此最优值为 。
快速检查
(为什么近似证明要对返回的赋值求值,而不是相信近似算法所提供的数值声明?)
想想可靠性陈述针对的是什么。
解答 · 答案
间隙的可靠性适用于实际的赋值。对输出求值可以验证其真实的值,并确保即使算法所报告的数值有误,该值也不会超过 no 情形的最优值。
快速检查
(在数值间隙例子中,为什么仅有 的近似比不能得出所述的阈值论证?)
把肯定输出的保证值与否定输出的最优值比较。
解答 · 答案
在 yes 输出上,保证值将仅为 ,低于 no 情形的上界 。这两个范围重叠,所以仅凭该保证无法区分这两种情形。
快速检查
(解释为什么在验证者选取了其随机查询位置之后,PCP 证明不能被更改。)
回想可靠性界所量化的对象。
解答 · 答案
可靠性界的是:对验证者的随机硬币而言,每个固定证明被接受的概率。若所谓的证明可以在看到查询之后自适应地作出回应,则模型及其量词都会不同,所陈述的 PCP 保证就不再适用。