For non-negative integers q, let PCP(q) denote the set of promise problems
that have polynomial-length probabalistically checkable proofs
over the binary alphabet in which the verifier only reads q bits.
(with no restriction on the amount of randomness that the verifier can use)

Let sPCP(q) denote the analogous class in which the verifier has
perfect completeness and chooses the bits to read non-adaptively.
(sPCP stands for "strong PCP", a term I made up for this question)

Obviously, $\:$PCP(0) = promiseBPP$\:$.
It is slightly less obvious, but still easy to show, that $\:$PCP(1) = promiseBPP$\:$.
It is known, though highly non-trivial, that $\:$NP $\subseteq$ sPCP(3)$\:$.
Since $\:$2SAT $\in$ P$\:$, $\:$ one has $\:$sPCP(2) $\subseteq$ promise-coRP$\:$ by reasoning similar to the PCP(1) equality.
However, that does yield any comparison between PCP(2) and NP.

Is either $\;\;\;$NP $\subseteq$ PCP(2) $\:$ or $\:$ PCP(2) $\subset$ NP$\;\;\;$ known to hold under plausible assumptions,
such as the promise versions of $\:$ P = BPP $\subset$ NP = MA ≠ coNP $\:$ ?

  • 2
    $\begingroup$ doesn't the hardness of approximation of MaxCUT give a 2-bit PCP for NP with constant gap between completeness and soundness? $\endgroup$ Jan 10, 2014 at 4:19
  • $\begingroup$ I think one would need a way to approximate how large of a cut there $\hspace{1.61 in}$ should be assuming the instance is true. $\:$ $\endgroup$
    – user6973
    Jan 10, 2014 at 4:36
  • 2
    $\begingroup$ Not sure what you mean: the NP-hardness of approximating MaxCut is proved via a gap problem, i.e. it is NP-hard to distinguish between a $c$ fraction of the edges being cut vs. $s$ fraction being cut. $c$ is the completeness, $s$ is the soundness, and bounds on both are given by the reduction. see e.g. theorem 5.14. in Hastad's paper: csce.uark.edu/~dapon/lib/Hastad.pdf $\endgroup$ Jan 10, 2014 at 5:43
  • $\begingroup$ After reading your first comment, I was looking at that paper and trying to find if there was anything in it which would work. $\:$ How does one go from that theorem to the NP-hardness of such a gap problem? $\:$ (It is not clear to me how one would find the relevant $c$ and $s$ to give a gap problem.) $\;\;\;$ $\endgroup$
    – user6973
    Jan 10, 2014 at 5:54
  • $\begingroup$ in the reduction, each equation over 3 variables is replaced by 16 equations over 2 variables, so that if the original equation is satisfiable, 12 of the new ones are satisfiable, and if it is not, 10 of them are. since we start with equations given by Hastad's 3-bit PCP where $c = 1-\delta$, $s \leq \frac{1}{2} + \delta$, after the reduction we have $c = \frac{3}{4}-\frac{1}{8}\delta$ and $s \leq \frac{11}{16} + \frac{1}{8}\delta$. $\endgroup$ Jan 10, 2014 at 13:25

1 Answer 1


Such a characterization of NP follows from the NP-hardness of any gap problem for a binary CSP with constraints of arity 2.

A binary CSP with arity 2 constraints is given by a family $\Pi$ of arity 2 relations on $\{0, 1\}^n$. An instance is given by a set of constraints. The GapCSP$_\Pi$($c$,$s$) problem for the CSP is the promise problem of distinguishing between CSP instances where at least a fraction $c$ of the constraints can be satisfied and instances where at most a fraction $s$ of the constraints can be satisfied. If such a GapCSP$_\Pi$($c$, $s$) problem is NP-hard for constants $c > s$, then we get a 2-bit PCP for NP in the usual way: the proof is a variable assignment, and can be verified by sampling a constraint and checking if it is satisfied.

In Some Optimal Inapproximability Results, Håstad shows that the GapCSP$_\Pi$($\frac{3}{4} - \delta$, $\frac{11}{16} + \delta$) problem is NP-hard for any constant $\delta$ when $\Pi$ is the family of constraints of the type $x_i + x_j = c \pmod 2$. There are two components to the reduction:

  • the famous optimal hardness of 3-variable linear equations mod 2: $\text{GapCSP}{_\Pi}$($1 - \delta'$, $\frac{1}{2} + \delta'$) is NP-hard for any constant $\delta'$ and $\Pi$ the family of constraints of the type $x_i + x_j + x_k = c \pmod 2$ (equivalently, this is a result about optimal 3-bit PCP for NP)

  • a gadget reduction from 3-variable linear equations to 2-variable linear equation; each 3-variable equation is replaced by sixteen 2-variable equations over the original variables and some auxiliary ones, so that if the original equation is satisfied, then 12 of the new equations can be satisfied by some assignment of the auxiliary variables, and if the original equation is not satisfied, then no assignment of the auxiliary variables satisfies more than 10 of the new equations (Theorem 5.14 in the paper)

You can get a better ratio between $c$ and $s$ if you assume the Unique Games conjecture: Khot, Kindler, O'Donnel, and Mossel showed that for $\Pi$ the max cut constraints $x_i \neq x_j$, solving GapCSP$_\Pi$($\frac{1}{2}(1 - \rho)$, $\frac{1}{\pi}\arccos(\rho) - \delta$) is as hard as Unique Games for any $\rho \in (-1, 1)$ and any constant $\delta > 0$. Optimizing over $\rho$ gives $\frac{s}{c}$ arbitrarily close to the Goemans-Williamson constant.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy