PCPs with imperfect completeness

Question

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?

Answer 1

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.

Answer 2

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.