<p>Yes, they have been studied before, such as in this paper:</p>

<blockquote>
  <p>M. Bellare, O. Goldreich and M. Sudan.  <a href="http://people.csail.mit.edu/madhu/papers/1995/bgs-journ.pdf" rel="noreferrer">Free bits, PCPs and non-approximability -- towards tight results</a>.  SIAM Journal on Computing, 1998.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-08T14:44:36.327Z
2010-11-08T14:57:16.490Z
2010-11-08T14:57:16.490Z
John Watrous
<p>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.  </p>

<p>Here are some examples:</p>

<ul>
<li><p><strong>The Unique Games Conjecture.</strong> 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).</p></li>
<li><p><strong>Linear equations.</strong> Linear equations with perfect completeness are easy (using Gaussian elimination), so hardness results for linear equations (e.g., Hastad's) focus on imperfect completeness.</p></li>
</ul>

CC BY-SA 2.5
2010-11-08T16:23:01.130Z
2010-11-08T16:23:01.130Z
Dana Moshkovitz
<p>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:</p>

<blockquote>
  <p>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:</p>
  
  <ul>
  <li>If $x\in L$, then there exists a $\pi$ that makes the verifier accept
  with probability at least $3/4$. </li>
  <li>If $x\notin L$, then for every proof $\pi$, the verifier accepts with
  probability at most $1/4$.</li>
  </ul>
</blockquote>

<p>There is an easy reduction from $3SAT$ to $\text{Max}2SAT$ (<a href="http://www.cs.uiuc.edu/class/sp09/cs579/assignments/hw-1.pdf" rel="nofollow">problem 5 in this</a>) that gives a simple $iPCP$ for $3SAT$. <strike>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$).</strike>  (thanks to Peter Shor for pointing this out)</p>

<p>Have such incomplete PCPs been studied earlier? </p>

CC BY-SA 2.5
2010-11-08T13:20:55.223Z
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.
Peter Shor 
CC BY-SA 2.5
2010-11-08T13:50:58.217Z
Oh yes, ... sorry for this goof-up. Thanks for pointing it out
Ramprasad
<cc.complexity-theory><reductions><pcp>
PCPs with imperfect completeness
Ramprasad
# PCPs with imperfect completeness

(Asked by: username_0 on 2010-11-08)

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](http://www.cs.uiuc.edu/class/sp09/cs579/assignments/hw-1.pdf)) 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?

**Tags:** cc.complexity-theory, reductions, pcp
> **Comments:**
> **username_1**: 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.  
> **username_0**: Oh yes, ... sorry for this goof-up. Thanks for pointing it out  

---

## 2 answers

### Answer by username_3 on 2010-11-08. Score: 14 | Accepted answer

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 by username_2 on 2010-11-08. Score: 11

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](http://people.csail.mit.edu/madhu/papers/1995/bgs-journ.pdf). 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.


---

