Can NP-hard statements be proved by PCPs that only involve reading 2 bits?

Question

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 $\:$ ?

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.