<p>Allowing completeness error has no problem, and it is often considered.  <a href="https://cstheory.stackexchange.com/questions/2780/pcps-with-imperfect-completeness">Here are some pointers</a>.</p>

<p>On the other hand, generally speaking, disallowing soundness error removes the power of a model significantly.</p>

<p>In the case of interactive proof systems, disallowing soundness error renders interaction useless except for one-way communication from a prover to a verifier; that is, IP with perfect soundness is equal to NP.  This can be shown by considering an NP machine which guesses the verifier’s random bits and the transcript of the interaction which make the verifier accept [FGMSZ89].</p>

<p>In the case of probabilistically checkable proof (PCP) systems, the same reasoning shows that requiring perfect soundness makes randomness useless for choosing the locations to query.  More precisely, it can be shown that PCP(<i>r</i>(<i>n</i>), <i>q</i>(<i>n</i>)) with completeness <i>c</i>(<i>n</i>) and perfect soundness (even with adaptive queries) is equal to the class <i>C</i> of decision problems <i>A</i>=(<i>A</i><sub>yes</sub>, <i>A</i><sub>no</sub>) for which there exists a language <i>B</i> ⊆ {0,1}*×{0,1}*×{0,1}* in P such that</p>

<ul>
<li>if <i>x</i>∈<i>A</i><sub>yes</sub>, then Pr<sub><i>y</i>∈{0,1}<sup><i>r</i>(<i>n</i>)</sup></sub>[∃<i>z</i>∈{0,1}<sup><i>q</i>(<i>n</i>)</sup> such that (<i>x</i>, <i>y</i>, <i>z</i>)∈<i>B</i>] ≥ <i>c</i>(<i>n</i>), and</li>
<li>if <i>x</i>∈<i>A</i><sub>no</sub>, then ∀<i>y</i>∈{0,1}<sup><i>r</i>(<i>n</i>)</sup> ∀<i>z</i>∈{0,1}<sup><i>q</i>(<i>n</i>)</sup>, (<i>x</i>, <i>y</i>, <i>z</i>)∉<i>B</i>,</li>
</ul>

<p>where <i>n</i>=|<i>x</i>|.  (Note that in the definition of class <i>C</i>, the yes case does not require a whole certificate to be prepared before the verifier picks the random string <i>y</i>, unlike the usual definition of a PCP system.  A certificate can be prepared after knowing <i>y</i>, and only the queried portion of the certificate is needed, which is why the length of <i>z</i> is <i>q</i>(<i>n</i>).)  Combined with straightforward lower bounds, this implies the following:</p>

<ul>
<li>PCP(log, log) with perfect soundness = P.</li>
<li>PCP(poly, log) with perfect soundness = <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:R#rp" rel="nofollow noreferrer">RP</a>.</li>
<li>PCP(poly, poly) with perfect soundness = NP.</li>
</ul>

<p>Comparing these to the PCP theorems PCP(log, O(1)) = NP and PCP(poly, O(1)) = NEXP, we can see that requiring perfect soundness has a huge impact.</p>

<p>[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos.  On completeness and soundness in interactive proof systems.  In <em>Randomness and Computation</em>, vol. 5 of <em>Advances in Computing Research</em>, pp. 429–442, 1989.  <a href="http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps" rel="nofollow noreferrer">http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps</a></p>

CC BY-SA 3.0
2012-09-21T00:13:14.430Z
2012-09-25T12:59:05.153Z
2017-04-13T12:32:28.077Z
Tsuyoshi Ito
<p>In most probabilistic proof systems ( PCP theorem, for instance), the error-probabilities are usually defined on the side of the false-positives, i.e., a typical definition could look like :  if $x \in L$ then the verifier always accepts, but in other case the probability of rejection is at least 1/2. </p>

<p>Is there a problem in allowing the error to happen on the other side ? That means the verifier always rejects when it should, and makes no more than a constant error when it needs to accept. Another obvious possibility is allowing the error on both sides.
Will these definitions be equivalent to the one usually given? Or, they behave differently ? Or for that matter, is there a genuine problem in allowing the errors on the other side.?</p>

CC BY-SA 3.0
2012-09-20T23:31:01.740Z
Why the downvote? Some PCPs don't have perfect completeness. On the other hand, there are some reductions with perfect soundness but not perfect completeness ("Free bits etc.", Bellare + Goldreich + Sudan, p. 21, last paragraph).
Yuval Filmus
CC BY-SA 3.0
2012-09-20T23:53:20.547Z
@Yuval Filmus: There are [many versions](http://www.wisdom.weizmann.ac.il/~oded/p_bgs.html) of the paper which you mentioned.  Which version are you referring to?
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-21T00:36:01.170Z
Thanks much to both of you for answers. I guess the downvote came from a perception that it isn't "research" question. It isn't indeed. Anyway, I cannot even upvote the answer with my reputation score, that got even reduced today :)
Arnab
CC BY-SA 3.0
2012-09-21T02:06:11.460Z
@TsuyoshiIto In version 2, it is on the bottom of page 22 (page 24 of the file).
Yuval Filmus
CC BY-SA 3.0
2012-09-21T03:11:42.087Z
@Yuval Filmus: Thanks.  The authors indeed mention probabilistic reductions with perfect soundness, but are they related to PCP systems with perfect soundness?
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-21T04:36:32.137Z
I have no idea. I just googled "perfect soundness".
Yuval Filmus
CC BY-SA 3.0
2012-09-21T15:42:16.690Z
@Yuval Filmus: I thought, probably incorrectly, that you were implying that probabilistic reductions with perfect soundness had something to do with PCP systems with perfect soundness.
Tsuyoshi Ito
<cc.complexity-theory><pcp><interactive-proofs>
One-sided errors in probablistic proof systems
Arnab
# One-sided errors in probablistic proof systems

(Asked by: username_0 on 2012-09-20)

In most probabilistic proof systems ( PCP theorem, for instance), the error-probabilities are usually defined on the side of the false-positives, i.e., a typical definition could look like : if $x \in L$ then the verifier always accepts, but in other case the probability of rejection is at least 1/2.

Is there a problem in allowing the error to happen on the other side ? That means the verifier always rejects when it should, and makes no more than a constant error when it needs to accept. Another obvious possibility is allowing the error on both sides.
Will these definitions be equivalent to the one usually given? Or, they behave differently ? Or for that matter, is there a genuine problem in allowing the errors on the other side.?

**Tags:** cc.complexity-theory, pcp, interactive-proofs

> **Comments:**
> **username_1**: Why the downvote? Some PCPs don't have perfect completeness. On the other hand, there are some reductions with perfect soundness but not perfect completeness ("Free bits etc.", Bellare + Goldreich + Sudan, p. 21, last paragraph).  
> **username_2**: @username_1: There are [many versions](http://www.wisdom.weizmann.ac.il/~oded/p_bgs.html) of the paper which you mentioned.  Which version are you referring to?  
> **username_0**: Thanks much to both of you for answers. I guess the downvote came from a perception that it isn't "research" question. It isn't indeed. Anyway, I cannot even upvote the answer with my reputation score, that got even reduced today :)  
> **username_1**: @TsuyoshiIto In version 2, it is on the bottom of page 22 (page 24 of the file).  
> **username_2**: @username_1: Thanks.  The authors indeed mention probabilistic reductions with perfect soundness, but are they related to PCP systems with perfect soundness?  
> **username_1**: I have no idea. I just googled "perfect soundness".  
> **username_2**: @username_1: I thought, probably incorrectly, that you were implying that probabilistic reductions with perfect soundness had something to do with PCP systems with perfect soundness.  

---

## 1 answers

### Answer by username_2 on 2012-09-21. Score: 12 | Accepted answer

Allowing completeness error has no problem, and it is often considered. [Here are some pointers](https://cstheory.stackexchange.com/questions/2780/pcps-with-imperfect-completeness).

On the other hand, generally speaking, disallowing soundness error removes the power of a model significantly.

In the case of interactive proof systems, disallowing soundness error renders interaction useless except for one-way communication from a prover to a verifier; that is, IP with perfect soundness is equal to NP. This can be shown by considering an NP machine which guesses the verifier’s random bits and the transcript of the interaction which make the verifier accept [FGMSZ89].

In the case of probabilistically checkable proof (PCP) systems, the same reasoning shows that requiring perfect soundness makes randomness useless for choosing the locations to query. More precisely, it can be shown that PCP(*r*(*n*), *q*(*n*)) with completeness *c*(*n*) and perfect soundness (even with adaptive queries) is equal to the class *C* of decision problems *A*=(*A*yes, *A*no) for which there exists a language *B* ⊆ {0,1}\*×{0,1}\*×{0,1}\* in P such that

* if *x*∈*A*yes, then Pr*y*∈{0,1}*r*(*n*)[∃*z*∈{0,1}*q*(*n*) such that (*x*, *y*, *z*)∈*B*] ≥ *c*(*n*), and
* if *x*∈*A*no, then ∀*y*∈{0,1}*r*(*n*) ∀*z*∈{0,1}*q*(*n*), (*x*, *y*, *z*)∉*B*,

where *n*=|*x*|. (Note that in the definition of class *C*, the yes case does not require a whole certificate to be prepared before the verifier picks the random string *y*, unlike the usual definition of a PCP system. A certificate can be prepared after knowing *y*, and only the queried portion of the certificate is needed, which is why the length of *z* is *q*(*n*).) Combined with straightforward lower bounds, this implies the following:

* PCP(log, log) with perfect soundness = P.
* PCP(poly, log) with perfect soundness = [RP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:R#rp).
* PCP(poly, poly) with perfect soundness = NP.

Comparing these to the PCP theorems PCP(log, O(1)) = NP and PCP(poly, O(1)) = NEXP, we can see that requiring perfect soundness has a huge impact.

[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos. On completeness and soundness in interactive proof systems. In *Randomness and Computation*, vol. 5 of *Advances in Computing Research*, pp. 429–442, 1989. <http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps>


---

