PCP 定理

形式陈述 ​

PCP 定理的标准类等式为

$$\mathbf{NP}=PC{P}_{1,1/2}(O(\log n),O(1)).$$

也就是说，对每个 $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$ 增长。反向包含成立，因为 NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 机器可猜出整份多项式证明，再枚举全部 $2^{O(\log n)}=\mathrm{poly}(n)$ 个随机串并精确计算接受比例；只猜一条接受随机路径不足以利用 soundness gap。

本页选 Dinur 的 gap-amplification 路线给可核验骨架，而不伪装成完整技术证明。第一步用 Cook–Levin 型归约把 NP 计算变为多项式大小、常数字母表的约束图；yes 实例全部约束可满足，但普通 no 实例可能只违反一个约束。第二步反复做 gap amplification：图 powering 让短随机游走同时检查多条约束，把很小的不可满足比例放大；degree reduction 用 expander 替换高次数变量并加一致性约束，保持规模和局部度受控；alphabet reduction 与 assignment tester 把膨胀的复合字母重新编码为常数字母表，并保证远离合法编码时有常数比例局部测试失败。迭代保持 perfect completeness，把 soundness gap 提升为固定 $\epsilon >0$，总证明长度仍为多项式。

得到常数 gap CSP 后，验证者用 $O(\log n)$ 随机位均匀选择多项式多个约束之一，查询该约束涉及的常数个 proof symbol。Yes 情形永远通过；No 情形至少 $\epsilon$ 比例约束失败，故接受概率至多 $1-\epsilon$。再用常数次误差放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。降到 $1/2$，查询数仍为常数。

直觉 ​

PCP 定理不是说原始 NP 见证随便抽几位就能验证，而是证明见证可以重编码为高度冗余的约束系统。Gap amplification 把一个局部谎言扩散成常数比例错误，局部测试再让随机抽样有固定概率碰到证据。

随机位数为 $O(\log n)$，因此验证者只能在多项式多个检查位置中选择；查询数为 $O(1)$，因此每次只读常数信息。两个参数控制不同资源，不能互换。

例子与边界 ​

直接对 Cook–Levin 公式随机抽一条子句不够：一个不可满足实例可能有某个赋值只违反 $m$ 条子句中的一条，单次抽查发现错误的概率只有 $1/m$，随规模趋零。PCP 构造的真实任务是把这种“几乎满足但仍为 no”的情况变成至少 $\epsilon m^{\prime }$ 条局部约束必然失败。

若验证者查询的是未经编码的普通 SAT 赋值，常数查询无法确认所有变量和子句的全局一致性。Assignment tester 需要同时检查局部约束和不同位置对同一逻辑值的编码一致性；只做前者会让证明在不同检查中给出互相矛盾的局部答案。

完整证明的深处是 gap amplification、expander 性质与 alphabet reduction 的参数闭环。本页明确这些模块的输入输出和保持量，但不声称几段文字替代其技术证明。不同 PCP 证明路线的中间参数不同，不能把 ALMSS 的低度测试常数与 Dinur 的图放大步骤混接。

推论与应用 ​

PCP 定理把 NP 的精确可满足性转化为常数 gap 可满足性，是许多不可近似结果的共同源头。具体优化问题仍需 gap-preserving reduction；类等式不会自动给每个问题一个近似阈值。

查询常数不表示验证总时间为常数：验证者仍需读取输入、计算查询位置并处理随机性。证明长度、随机位、查询数、字母表和 soundness 都应一起报告。

参考资料

• 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.
• Irit Dinur, “The PCP Theorem by Gap Amplification,” Journal of the ACM 54(3), 2007, Article 12.