10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Sep 20 '12 at 23:31
  • $\begingroup$ @Yuval Filmus: There are many versions of the paper which you mentioned. Which version are you referring to? $\endgroup$ – Tsuyoshi Ito Sep 20 '12 at 23:53
  • $\begingroup$ 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 :) $\endgroup$ – Arnab Sep 21 '12 at 0:36
  • $\begingroup$ @TsuyoshiIto In version 2, it is on the bottom of page 22 (page 24 of the file). $\endgroup$ – Yuval Filmus Sep 21 '12 at 2:06
  • 1
    $\begingroup$ I have no idea. I just googled "perfect soundness". $\endgroup$ – Yuval Filmus Sep 21 '12 at 4:36
12
$\begingroup$

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=(Ayes, Ano) for which there exists a language B ⊆ {0,1}*×{0,1}*×{0,1}* in P such that

  • if xAyes, then Pry∈{0,1}r(n)[∃z∈{0,1}q(n) such that (x, y, z)∈B] ≥ c(n), and
  • if xAno, 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.