17
$\begingroup$

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

$\endgroup$
19
$\begingroup$

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.

$\endgroup$
22
$\begingroup$

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.

$\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.