<p>It depends a bit how you define the PCP Theorem, is it with perfect completeness or not. As we state in our book, an equivalent form of the PCP Theorem is that there is some constraint satisfaction problem for which it's NP-hard to distinguish between the perfect satisfiable case and the case that one can satisfy at most some fraction $s&lt;1$ of the cosntraints. But, we could have state a variant with imperfect completeness, replacing the perfect satisfiable case with being able to satisfy some fraction $c&gt;s$.</p>

<p>The unique games conjecture is an assumption of this latter form (where, making the condition stronger $c$ is close to $1$ and $s$ is close to $0$) and, most importantly, the constraints are of a very special form (permutation constraints on two variables). In that sense it's (essentially) stronger form of the PCP Theorem. </p>

<p>You can ask if there's an easy transformation to convert a PCP with imperfect completeness to one with perfect completeness. I think it probably can be done easier than proving the PCP Theorem, but I'm not aware at the moment of a very simple argument.</p>

CC BY-SA 2.5
2011-04-02T01:54:00.163Z
2011-04-02T01:54:00.163Z
Boaz Barak
<p>The related $2-1$-conjecture of Khot implies the PCP theorem with perfect completeness: The proof is expected to give a labeling of the vertices. The verifier selects a random edge queries its endpoints and accepts iff the constraint holds. </p>

<p>For getting a PCP theorem with perfect completeness from the unique games conjecture you need to, as Boaz writes, convert a $(c,s)$ PCP into one with perfect completeness. One way to do that is:</p>

<p>Add new variables one per constraint, and modify the constraint to be satisfied if either the new variable is true, or else if the constraint were previously satisfied. Now the question is reduced to finding a PCP for deciding if a set of m bits (=the new vars) has sum at most $(1-c)\cdot m$ or at least $(1-s)\cdot m$. This seems like a non-trivial question, but easier than the PCP theorem. </p>

CC BY-SA 3.0
2012-02-14T17:20:44.677Z
2012-02-14T17:20:44.677Z
Irit Dinur
<p>how can one show that what is relation between "Unique games conjecture" and "PCP theorem"?
how does one explain "Unique games conjecture" is stronger form of "PCP theorem"?</p>

<cc.complexity-theory><pcp><unique-games-conjecture>
Is there a simple argument that shows that  the unique games conjecture implies the PCP theorem
j.s.
# Is there a simple argument that shows that  the unique games conjecture implies the PCP theorem

(Asked by: username_0 on 2011-03-11)

how can one show that what is relation between "Unique games conjecture" and "PCP theorem"?
how does one explain "Unique games conjecture" is stronger form of "PCP theorem"?

**Tags:** cc.complexity-theory, pcp, unique-games-conjecture


---

## 2 answers

### Answer by username_2 on 2012-02-14. Score: 20 | Accepted answer

The related $2-1$-conjecture of Khot implies the PCP theorem with perfect completeness: The proof is expected to give a labeling of the vertices. The verifier selects a random edge queries its endpoints and accepts iff the constraint holds.

For getting a PCP theorem with perfect completeness from the unique games conjecture you need to, as Boaz writes, convert a $(c,s)$ PCP into one with perfect completeness. One way to do that is:

Add new variables one per constraint, and modify the constraint to be satisfied if either the new variable is true, or else if the constraint were previously satisfied. Now the question is reduced to finding a PCP for deciding if a set of m bits (=the new vars) has sum at most $(1-c)\cdot m$ or at least $(1-s)\cdot m$. This seems like a non-trivial question, but easier than the PCP theorem.


---

### Answer by username_1 on 2011-04-02. Score: 23

It depends a bit how you define the PCP Theorem, is it with perfect completeness or not. As we state in our book, an equivalent form of the PCP Theorem is that there is some constraint satisfaction problem for which it's NP-hard to distinguish between the perfect satisfiable case and the case that one can satisfy at most some fraction $s<1$ of the cosntraints. But, we could have state a variant with imperfect completeness, replacing the perfect satisfiable case with being able to satisfy some fraction $c>s$.

The unique games conjecture is an assumption of this latter form (where, making the condition stronger $c$ is close to $1$ and $s$ is close to $0$) and, most importantly, the constraints are of a very special form (permutation constraints on two variables). In that sense it's (essentially) stronger form of the PCP Theorem.

You can ask if there's an easy transformation to convert a PCP with imperfect completeness to one with perfect completeness. I think it probably can be done easier than proving the PCP Theorem, but I'm not aware at the moment of a very simple argument.


---

