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 the definition as follows:

A language $L$ is in $iPCP(r,q)$ such that there exists a verifier who tosses $r$ coins and queries $q$ locations of a proof $\pi$ such that:

  • If $x\in L$, then there exists a $\pi$ that makes the verifier accept with probability at least $3/4$.
  • If $x\notin L$, then for every proof $\pi$, the verifier accepts with probability at most $1/4$.

There is an easy reduction from $3SAT$ to $\text{Max}2SAT$ (problem 5 in this) that gives a simple $iPCP$ for $3SAT$. And by definition, the class is closed under complement so it includes $coNP$ as well. Therefore, it is unlikely that there is a way to convert an $iPCP$ to a $PCP$ with the same parameters (well, that would at least mean $coNP = NP$). (thanks to Peter Shor for pointing this out)

Have such incomplete PCPs been studied earlier?

  • $\begingroup$ This isn't closed under complement. If you complement it, you interchange there exists and for every in your conditions, as well as the 1/4 and 3/4. $\endgroup$ – Peter Shor Nov 8 '10 at 13:20
  • $\begingroup$ Oh yes, ... sorry for this goof-up. Thanks for pointing it out $\endgroup$ – Ramprasad Nov 8 '10 at 13:50

Yes, PCPs with imperfect completeness have been studied before. The main motivation is that for some natural and interesting problems, finding whether there is a perfect solution is actually easy (polynomial-time), while approximating the best solution, if this best solution is not perfect, is (or believed to be) hard.

Here are some examples:

  • The Unique Games Conjecture. Unique games with perfect completeness are easy, so the Unique Games Conjecture focuses on unique games with imperfect completeness. Feige and Reichman showed NP-hardness for unique games for some constant completeness and soundness values (not c=1-delta s=epsilon as conjectured).

  • Linear equations. Linear equations with perfect completeness are easy (using Gaussian elimination), so hardness results for linear equations (e.g., Hastad's) focus on imperfect completeness.

| cite | improve this answer | |

Yes, they have been studied before, such as in this paper:

M. Bellare, O. Goldreich and M. Sudan. Free bits, PCPs and non-approximability -- towards tight results. SIAM Journal on Computing, 1998.

Various results are proved in this paper about classes of the form $\mathrm{PCP}_{c,s}[r,q]$, which denotes the class of promise problems having a PCP where the verifier flips $r$ coins, makes $q$ queries, and has completeness and soundness probabilities $c$ and $s$, respectively.

Someone with greater expertise in this area could point you to more recent references that are relevant, but this was surely an important and influential early paper in the area.

| cite | improve this answer | |

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.