Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

Question

In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables. For a constant 0<s<1, Gap-3SAT_s is the following promise problem:

Gap-3SAT_s
Instance: A 3CNF formula φ.
Yes-promise: φ is satisfiable.
No-promise: No truth assignments satisfy more than s fraction of the clauses of φ.

One of the equivalent ways to state the celebrated PCP theorem [AS98, ALMSS98] is that there exists a constant 0<s<1 such that Gap-3SAT_s is NP-complete.

We say that a 3CNF formula is pairwise B-bounded if every pair of distinct variables appears in at most B clauses. For example, a 3CNF formula (x₁∨x₂∨x₄)∧(￢x₁∨￢x₃∨x₄)∧(x₁∨x₃∨￢x₅) is pairwise 2-bounded but not pairwise 1-bounded because e.g. the pair (x₁, x₄) appears in more than one clause.

Question. Do there exist constants B∈ℕ, a>0, and 0<s<1 such that Gap-3SAT_s is NP-complete even for a 3CNF formula which is pairwise B-bounded and consists of at least an² clauses, where n is the number of variables?

The pairwise boundedness clearly implies that there are only O(n²) clauses. Together with the quadratic lower bound on the number of clauses, it roughly says that no pair of distinct variables appears in significantly more clauses than the average.

For Gap-3SAT, it is known that the sparse case is hard: there exists a constant 0<s<1 such that Gap-3SAT_s is NP-complete even for a 3CNF formula where each variable occurs exactly five times [Fei98]. On the other hand, the dense case is easy: Max-3SAT admits a PTAS for a 3CNF formula with Ω(n³) distinct clauses [AKK99], and therefore Gap-3SAT_s in this case is in P for every constant 0<s<1. The question asks about the middle of these two cases.

The above question arose originally in a study of quantum computational complexity, more specifically two-prover one-round interactive proof systems with entangled provers (MIP^*(2,1) systems). But I think that the question may be interesting in its own right.

References

[AKK99] Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instance of NP-hard problems. Journal of Computer and System Sciences, 58(1):193–210, Feb. 1999. http://dx.doi.org/10.1006/jcss.1998.1605

[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501–555, May 1998. http://doi.acm.org/10.1145/278298.278306

[AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70–122, Jan. 1998. http://doi.acm.org/10.1145/273865.273901

[Fei98] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, July 1998. http://doi.acm.org/10.1145/285055.285059

Answer 1

Not a full answer, but hopefully close. This is very close to Luca's comments above. I believe the answer is that at least there do exist constants B∈ℕ, a>0, and 0<s<1 such that Gap-3SAT_s is NP-complete even for a 3CNF formula which is pairwise B-bounded and consists of at least $an^{2-\epsilon}$ clauses, for any constant $\epsilon$.

The proof is as follows. Consider a GAP-3SAT$_s$ instance $\phi$ on $N$ variables in which each variable appears at most 5 times. This is NP-complete, as you say in the question.

Now we create a new instance $\Phi$ as follows:

1. For every variable $x_i$ in $\phi$, $\Phi$ has $n$ variables $y_{ij}$.
2. For every set of indices $i$, $a$ and $b$ with $a\neq b$, $\Phi$ has a pair of clauses $y_{ia}∨￢y_{ib}∨￢y_{ib}$, and $y_{ib}∨￢y_{ia}∨￢y_{ia}$. I'll refer to these as comparison clauses since they ensure that $y_{ia} = y_{ib}$ if they are satisfied.
3. For every clause in $\phi$ acting on variables $x_i$, $x_j$ and $x_k$, for every $a$ and $b$, $\Phi$ contains an equivalent clause, where $x_i$ is replaced by $y_{ia}$, $x_j$ is replaced by $y_{jb}$ and $x_k$ is replaced by $y_{k(a+b)}$ (here addition is done modulo $n$). I'll refer to these as inherited clauses.

The total number of variables is then $m = nN$. Note $\Phi$ has $2Nn^2$ comparison clauses and $\frac{5}{3}Nn^2$ inherited clauses, for a total of $\frac{11}{3}Nn^2$ clauses. Taking $n = N^k$ we have $m = N^{k+1}$ and the total number of clauses $C = \frac{11}{3}N^{2k+1} = \frac{11}{3}m^{2-\frac{1}{k+1}}$. We take $k = \epsilon^{-1} - 1$, so $C \propto m^{2-\epsilon}$.

Next, $\Phi$ is pairwise 8-bounded (max of 2 from the comparison clauses and 6 from the inherited clauses).

Finally, if $\phi$ is unsatisfiable, then at least $(1-s)N$ clauses are unsatisfied. Now, if $y_{ia} \neq y_{ib}$ for any $a,b$ then at least $n-1$ clauses are unsatisfied. Note that in order to satisfy the $(1-s)N$ unsatisfied clauses in a set of inherited clauses for fixed $a,b$ then the assignment of variables $y_{:a}$, $y_{:b}$ and $y_{:(a+b)}$ must differ at at least $\frac{1-s}{5}N$ positions, leaving at least $\frac{1-s}{5}N(n-1)$ comparison unsatisfiable clauses. This must hold for every choice of $a$ and $b$, so at least $\approx \frac{1-s}{5}Nn^2 = \frac{3(1-s)}{11}C$ comparison clauses must remain unsatisfied in total for enough inherited clauses to be satisfied. If however you look at the other extreme where all comparison clauses are satisfied, then $(1-s)Nn^2 = (1-s)m^{\frac{2k+1}{k+1}} = (1-s)C$ clauses are unsatisfiable. Hence a gap remains (although reduced) with $s' = \frac{4+s}{5}$.

The constants probably need to be double checked.