Sliding Scale Conjectures in PCP

摘要

The PCP (i.e., Probabilistically Checkable Proofs) Theorem [8, 7, 22, 5, 4] states that any mathematical proof can be converted to a format that can be checked by a verifier making only a constant number of queries to the proof. The verifier picks the queries in a randomized way and might err with low probability.