All Questions
Tagged with pcp reductions
1 question
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 ...