概率可检验证明

形式陈述 ​

设 $r,q:\mathbb{N}\to \mathbb{N}$。语言 $L$ 属于 $PC{P}_{c,s}(r(n),q(n))$，若存在多项式时间随机验证者 $V$，对长度 $n$ 的输入 $x$ 使用至多 $r(n)$ 个随机 bit，并把证明字符串 $\pi$ 作为只读 oracle 查询至多 $q(n)$ 个位置，且满足

$$\begin{array}{rl}x\in L& ⟹\mathrm{\exists }\pi {\text{Pr}}_R[V^{\pi }(x;R)=1]\ge c,\\ x\notin L& ⟹\mathrm{\forall }\pi {\text{Pr}}_R[V^{\pi }(x;R)=1]\le s,\end{array}$$

其中 $c>s$ 是 completeness 与 soundness 参数，概率只对验证者的随机串 $R$ 取。常写 $PCP(r,q)$ 省略固定常数，例如 $c=1,s=1/2$。本页采用非自适应查询约定：所有查询位置由 $(x,R)$ 决定；若允许后一个查询依赖先前读到的 proof bit，必须显式标为 adaptive PCP。

证明 oracle 在随机性产生前已经固定，不能看见查询后临时改答。验证者运行时间、随机 bit 数、查询数和证明长度是不同资源；给定多项式时间地址计算时，可访问位置的编码长度受多项式约束，但具体定理仍应声明证明长度保证。

直觉 ​

PCP 的目标不是从原始见证中随便抽几位，而是先把证明编码成带大量冗余和局部一致性约束的对象。随机性选择少量检查位置；若伪造证明在全局上远离任何合法编码，许多局部约束会被破坏，于是常数次抽查也有固定概率抓到错误。

局部读取不表示证明短，也不表示验证者与证明者交互。随机验证者公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。只访问一份预先写定的字符串；这一顺序正是 soundness 中“对所有 $\pi$，再对随机 $R$ 计概率”的含义。

例子与边界 ​

每个 $L\in \mathbf{P}$ 都有一个平凡 PCP：验证者忽略 $\pi$，不使用随机 bit，也不作查询，直接运行确定性判定算法，因此 completeness 为 $1$、soundness 为 $0$。这个正例说明定义允许零查询，却没有展示 PCP 的力量；真正重要的结论是把 NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 见证重新编码后仍能局部验证，那是独立定理而不是定义的一部分。

把普通 SAT 赋值原样当作 proof，再随机检查一个子句，并不能在一般公式上自动得到常数 soundness：一个不满足公式可能只违反极少数子句，随机抽查几乎总会错过。PCP 构造需要 gap amplification、低度测试或 proof composition 等机制，把全局错误扩散成可局部察觉的距离。

若 proof oracle 可以在看到查询后改变答案，两个互相矛盾的局部测试可能分别得到量身定制的回应，soundness 推导便失效；那更接近交互证明模型。重复独立运行验证者可以降低 soundness error，但会相应增加随机性和查询数，参数变化必须一并报告。

推论与应用 ​

PCP 记号把“随机多少、读多少、接受正确证明的概率、误收伪证明的概率”拆成可比较参数。它连接编码、局部测试和近似困难性：局部可检验约束提供常数 gap，归约再把这一 gap 传给优化问题。没有相应定理时，定义本身不保证任意 NP 语言具有常数查询证明。

与语言公理库形式语言Formal language · Language over an alphabet字母表上有限字符串集合的抽象，是自动机输入与计算问题编码的基本对象。的普通验证定义相比，PCP 把完整读取证书改为 oracle 查询；与交互证明相比，它没有多轮消息；与 property testing 相比，proof 是额外提供的辅助对象。三者都使用随机抽样，但量词顺序与被查询对象不同。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, Chs. 11 and 22.
• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, “Proof Verification and the Hardness of Approximation Problems,” Journal of the ACM 45(3), 1998, pp. 501–555.