Probabilistically checkable proofs, part 1
Kent Quanrud · 75:32
This lecture introduces probabilistically checkable proofs and the PCP theorem: every NP language has a polynomial-size proof that a verifier can check with only \(O(\log n)\) random bits and a constant number of quer...