有人能用外行的话来描述一下PCP Theorem吗？[编辑：我是一个计算机科学的学生开始理论。]
最佳答案
针对外行计算机科学家：
PCP定理说，你可以做证明，这是如此容易检查，你只需要看一个固定数量的（随机选择）位（通常）来区分一个坏的证明和一个好的证明。
针对外行理论家：
一种语言是np意味着你可以很容易地证明一个字符串是np语言。例如，可以通过提供一个布尔电路的满意输入来证明它是可满足的。（但很难证明一个电路是不可满足的！）
在这种情况下，验证证明的person/program/turing机器必须在多项式时间内运行（按照语言中的字符串大小）。它必须是完整的，这意味着它始终接受给定字符串在语言中的有效证明。它必须是健全的，这意味着它拒绝任何“证据”的字符串，不是在语言。
对于NP，验证器是确定性的如果验证者可以使用随机性呢？然后我们必须允许一些错误，所以我们允许验证器不完全正确——它可能不正确地接受一些证据。实际上，我们所关心的是验证者至少会检测到四分之一的错误证据。如果你想要更好的准确性，你可以经常运行几次：-）
pcp定理以其最强大的形式表示，np语言中的任何一种语言都有一个证明系统，只要看一个随机选择的恒定比特数就可以证明它。常数是…三。（这与3-SAT中的3个相同）这些校样使用纠错码，因此校样中的任何错误都会与很大一部分输入冲突。使用一个更强大的代码，你可以任意接近50%的可靠性，只有3位。