If the instance is positive, then there exits a proof such that the verifier answers Yes with probability one, while if the instance is a negative instance then for any proof then the verifier answers Yes with probability less than 1/2
| We say that
the decision problem P belongs to the class PCP [r,q]
if it admits a polynomial-time verifier A such that the verifier
uses (r) of n random bits if for any input of length n
the verifier queries q(n) bits of the proof If the instance is positive, then there exits a proof such that the verifier answers Yes with probability one, while if the instance is a negative instance then for any proof then the verifier answers Yes with probability less than 1/2 |
|
