PCP 定理

形式陈述 ​

沿用概率可检验证明（PCP）理路概率可检验证明Probabilistically checkable proof允许随机验证者把证明视为只读 oracle，并用受限随机位和局部查询区分正确与伪造证明的系统。对随机位数与查询数的定义，PCP 定理的标准类等式为

也就是说，对每个 $L\in \mathbf{NP}$，存在多项式时间随机验证者和多项式长度的只读证明 $\pi$：长度为 $n$ 的输入上使用至多 $c\log n$ 个随机 bit，非自适应查询至多常数 $q$ 个取自固定有限字母表的 proof symbol；若 $x\in L$，某个证明以概率 $1$ 被接受；若 $x\notin L$，任意证明的接受概率至多 $1/2$。常数 $c,q$ 与语言和构造有关，但不随 $n$ 增长；有限个小长度单独处理。固定有限字母表可以用常数个 bit 编码一个符号，查询只增加常数倍；读到非法编码时拒绝，因此不扩大伪证明的接受概率。

反向包含还需说明证明的可访问部分为何多项式大。枚举全部 $2^{O(\log n)}=\mathrm{poly}(n)$ 个随机串，每串至多给出 $q$ 个非自适应地址；对这些地址去重后，只有多项式多个位置，每个地址本身也只有多项式位长。NP理路复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 验证器可猜这些不同位置上的一致内容，再枚举全部随机串，要求每次检验都接受。完备性1保证 yes 时存在这份内容；soundness 至多1/2保证 no 时不可能全通过。即使原地址编号很大，也可以按这张有限表重新编号，不需要猜出地址空洞中的全部字符。只猜一条接受随机路径则没有同样保证。

下面概述 Dinur 证明的构造顺序，具体的预处理、powering 与 assignment-tester 引理见原论文。它从Cook–Levin 型归约理路Cook–Levin 定理Cook–Levin theorem · SAT is NP-complete布尔可满足性问题 SAT 是 NP 完全问题。开始，把 NP 计算变为多项式大小、常数字母表的约束图。Yes 实例的全部约束可同时满足；no 实例的每个赋值都至少违反一个约束，但违反比例可能只有规模的倒数。

随后迭代放大这个比例。预处理先用有界度扩张图理路扩张图Expander graph · Expander family每个不超过半数的顶点集合都向外暴露大量边或邻点的稀疏图及其有界度图族。连接变量的多个副本，以一致性约束控制度数，再叠加辅助扩张图的恒真约束，取得整个底层图的统一扩张保证，并完成所需正则化与自环处理。后一步只使不可满足比例损失常数倍；局部副本连接本身并不保证整体已是扩张图。在这些前提下，图 powering 让短随机游走同时检查多条约束，放大不可满足比例；alphabet reduction 再用 assignment tester 把增长的复合字母编码回常数字母表。各步保留完全可满足性，并以常数倍规模开销获得净的 gap 增长。经过对数轮迭代，gap 达到固定 $\epsilon >0$，总证明长度仍为多项式。

得到常数 gap CSP 后，可补入恒真约束，使约束总数成为二的幂；总数增加不到一倍，gap 至少保留为 $\epsilon /2$。验证者用 $O(\log n)$ 个随机位均匀选择一个约束，查询它涉及的常数个 proof symbol。Yes 情形永远通过，no 情形的接受概率至多为 $1-\epsilon /2$。再做常数次误差放大理路概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。，每轮使用新的独立随机位并要求所有轮都接受，把任意固定伪证明的接受概率降到 $1/2$，查询总数仍为常数。