Probabilistically checkable proofs, part 2 (Randomized algorithms, Fall 2022, Lecture 24)
Kent Quanrud · 79:03
The PCP theorem says NP = PCP(log n, O(1)): every NP language has a polynomial-size “robust” proof that a verifier can check by flipping logarithmically many random bits and reading only a constant number of proof bit...