Skip to main content

All Questions

Tagged with
Filter by
Sorted by
Tagged with
6 votes
2 answers
465 views

PCPs with imperfect completeness

The traditional definition of PCPs have perfect completeness -- If $x\in L$, then the prover can give a proof on which the verifier (on reading constantly many bits) always accepts. Suppose we modify ...
Ramprasad's user avatar
  • 2,492