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-3SATs is the following promise problem:

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-3SATs 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 (x1x2x4)∧(¬x1∨¬x3x4)∧(x1x3∨¬x5) is pairwise 2-bounded but not pairwise 1-bounded because e.g. the pair (x1, x4) appears in more than one clause.

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

The pairwise boundedness clearly implies that there are only O(n2) 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-3SATs 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 Ω(n3) distinct clauses [AKK99], and therefore Gap-3SATs 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.


[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

  • $\begingroup$ @Tsuyoshi: am I right in presuming that nothing is known about the other intermediate cases, between $m = O(n)$ and $m = \Omega(n^3)$? $\endgroup$ Oct 25 '10 at 14:17
  • 1
    $\begingroup$ @András: I am not aware of any prior results about intermediate cases, but I have what I think is a proof of the NP-completeness of the following cases. (1) Pairwise bounded, $\Omega(n^2)$ clauses, but without a gap. (2) With a gap, $\Omega(n^d)$ clauses for any constant d<3, but not necessarily pairwise bounded. (3) With a gap, pairwise bounded, $\Omega(n^d)$ clauses for any constant d<2. The proof of (1) is a simple reduction from [Fei98]. The proof of (2) uses part of the result by Ailon and Alon 2007. The proof of (3) uses expanders. $\endgroup$ Oct 26 '10 at 0:28
  • 1
    $\begingroup$ @Tsuyoshi: Looking forward to reading your paper. $\endgroup$ Oct 26 '10 at 10:12
  • 4
    $\begingroup$ Don't have an answer but I would check if the methods to certify that a random 3CNF of m clauses is unsatisfiable can succeed here in showing this problem is easy, at least if you required the soundness $s$ to be close to 7/8. These works succeed once there are more than $n^{1.5}$ clauses and have been extended to semi-random models (see Feige FOCS 07 on refuting smoothed 3CNF). However, it seems that Tsuyoshi showed that even the case of $n^{1.9}$ here is still NP-hard, so maybe this shows these works are not relevant. $\endgroup$
    – Boaz Barak
    Apr 2 '11 at 1:40
  • 7
    $\begingroup$ Boaz, you can always "densify" an instance of 3SAT by replacing every variable by $M$ copies, and then replacing every clause by $M^3$ clauses, replacing each variable in the original clause by copies in all possible ways. This gives you an instance in which the same fraction of clauses as before is satisfiable, but you go from n variables and m clauses to nM variables and $mM^3$ clauses, so, with no further constraint on the number of occurrences, you can keep the soundness $7/8 + \epsilon$ even in formulas with $N$ variables and $N^{2.999}$ clauses. $\endgroup$ Apr 2 '11 at 2:42

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-3SATs 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.

  • $\begingroup$ Thank you, Joe. Sorry if this was not clear, but in this question, I require the three variables in each clause to be all distinct, and therefore comparison clauses as they are written cannot be used. I have a proof of the same fact (pairwise bounded, Ω(n^(2−ε)) clauses, with gap) which uses expander graphs, but if it can be proved without using expanders, I am very interested. $\endgroup$ Sep 4 '11 at 13:10
  • $\begingroup$ @Tsuyoshi: Ah I see. Actually, I had initially proved it to myself with distinct variables, so there is a very easy tweek to get it into the form you want. You simple assign the comparison clauses in a slighty different manner. Instead of the two clauses I gave you need 4: $y_{ia}∨¬y_{ib}∨¬y_{i(a+b)}$, $y_{ia}∨¬y_{ib}∨y_{i(a+b)}$, $¬y_{ia}∨y_{ib}∨¬y_{i(a+b)}$ and $¬y_{ia}∨y_{ib}∨y_{i(a+b)}$. Clearly these reduce to the same 2 variable clauses as before. Obviously this tweeks the constants, but doesn't make any other difference. $\endgroup$ Sep 4 '11 at 14:10
  • $\begingroup$ Perhaps there is a way to get around the $\epsilon$ factor by taking $k = k(n)$, though the most naive implementation of this gives instances that grow very slightly faster than polynomially. $\endgroup$ Sep 4 '11 at 14:12
  • $\begingroup$ I will check the details more carefully later, but the idea of using a, b, and (a+b) seems to work. This should free me from dealing with expanders explicitly. Thanks! $\endgroup$ Sep 4 '11 at 14:23
  • $\begingroup$ No problem. Glad I could be of help. $\endgroup$ Sep 4 '11 at 14:31

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.