4.4.3 PCP 定理（Probabilistically Checkable Proof...

文档摘要

4.4.3 PCP 定理（Probabilistically Checkable Proofs）与近似硬度 4.4.3 PCP 定理（Probabilistically Checkable Proofs）与近似硬度想象一下，你是一位密码学家，正在设计一个零知识证明系统，却发现验证者只需随机瞥一眼证明，就能以高概率判断其正确性。这不是科幻，而是PCP定理的核心魔力。它将NP问题的证明从线性扫描转化为“懒验证者”的天堂：证明可以很长，但验证只需恒定查询。1992年，阿罗拉（Arora）、萨夫拉（Safra）、鲁道夫（Rudich）和萨克斯坦德（Saks）联手证明了这个定理，彻底重塑了计算复杂性理论。