One-sided errors in probablistic proof systems

Question

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.?

Answer 1

Allowing completeness error has no problem, and it is often considered. Here are some pointers.

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.
• 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