<p>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 <i>B</i>∈ℕ, <i>a</i>&gt;0, and 0&lt;<i>s</i>&lt;1 such that Gap-3SAT<sub><i>s</i></sub> is NP-complete even for a 3CNF formula which is pairwise <i>B</i>-bounded and consists of at least $an^{2-\epsilon}$ clauses, for any constant $\epsilon$.</p>

<p>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.</p>

<p>Now we create a new instance $\Phi$ as follows:</p>

<ol>
<li>For every variable $x_i$ in $\phi$, $\Phi$ has $n$ variables $y_{ij}$.</li>
<li>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. </li>
<li>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.</li>
</ol>

<p>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}$.</p>

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

<p>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&#39; = \frac{4+s}{5}$.</p>

<p>The constants probably need to be double checked.</p>

CC BY-SA 3.0
2011-09-04T13:10:24.843Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-04T14:10:06.247Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2011-09-04T14:12:34.417Z
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.
Joe Fitzsimons
CC BY-SA 3.0
2011-09-04T14:23:16.927Z
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!
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-04T14:31:18.273Z
No problem. Glad I could be of help.
Joe Fitzsimons
CC BY-SA 3.0
2011-09-04T07:53:20.190Z
2011-09-05T19:17:10.980Z
2011-09-05T19:17:10.980Z
Joe Fitzsimons
<p>In this question, a 3CNF formula means a CNF formula where each clause involves <em>exactly</em> three <em>distinct</em> variables.  For a constant 0&lt;<i>s</i>&lt;1, Gap-3SAT<sub><i>s</i></sub> is the following promise problem:</p>

<p><strong>Gap-3SAT<sub><i>s</i></sub></strong><br>
<em>Instance</em>: A 3CNF formula φ.<br>
<em>Yes-promise</em>: φ is satisfiable.<br>
<em>No-promise</em>: No truth assignments satisfy more than <i>s</i> fraction of the clauses of φ.</p>

<p>One of the equivalent ways to state the celebrated PCP theorem [AS98, ALMSS98] is that there exists a constant 0&lt;<i>s</i>&lt;1 such that Gap-3SAT<sub><i>s</i></sub> is NP-complete.</p>

<p>We say that a 3CNF formula is <em>pairwise B-bounded</em> if every pair of distinct variables appears in at most <i>B</i> clauses.  For example, a 3CNF formula (<i>x</i><sub>1</sub>∨<i>x</i><sub>2</sub>∨<i>x</i><sub>4</sub>)∧(￢<i>x</i><sub>1</sub>∨￢<i>x</i><sub>3</sub>∨<i>x</i><sub>4</sub>)∧(<i>x</i><sub>1</sub>∨<i>x</i><sub>3</sub>∨￢<i>x</i><sub>5</sub>) is pairwise 2-bounded but not pairwise 1-bounded because e.g. the pair (<i>x</i><sub>1</sub>, <i>x</i><sub>4</sub>) appears in more than one clause.</p>

<blockquote>
  <p><strong>Question</strong>.  Do there exist constants <i>B</i>∈ℕ, <i>a</i>&gt;0, and 0&lt;<i>s</i>&lt;1 such that Gap-3SAT<sub><i>s</i></sub> is NP-complete even for a 3CNF formula which is pairwise <i>B</i>-bounded and consists of at least <i>an</i><sup>2</sup> clauses, where <i>n</i> is the number of variables?</p>
</blockquote>

<p>The pairwise boundedness clearly implies that there are only O(<i>n</i><sup>2</sup>) 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.</p>

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

<p>The above question arose originally in a study of quantum computational complexity, more specifically two-prover one-round interactive proof systems with entangled provers (<a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aM#mipstar21">MIP<sup>*</sup>(2,1)</a> systems).  But I think that the question may be interesting in its own right.</p>

<p><strong>References</strong></p>

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

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

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

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

CC BY-SA 2.5
2011-04-02T01:40:59.860Z
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.
Boaz Barak
CC BY-SA 2.5
2011-04-02T02:42:50.400Z
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.
Luca Trevisan
CC BY-SA 3.0
2011-08-28T19:00:44.087Z
The link to the Complexity Zoo must have been broken for a long time!  Sorry for bumping the question without any update in the content.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-25T14:17:10.833Z
@Tsuyoshi: am I right in presuming that nothing is known about the other intermediate cases, between $m = O(n)$ and $m = \Omega(n^3)$?
András Salamon
CC BY-SA 2.5
2010-10-26T00:28:40.667Z
@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](http://dx.doi.org/10.1016/j.ic.2007.02.006). The proof of (3) uses expanders.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-26T10:12:54.310Z
@Tsuyoshi: Looking forward to reading your paper.
András Salamon
CC BY-SA 2.5
2010-10-26T12:18:11.517Z
@András: Uh-oh.  Currently I have no plan to write up a paper from these results.  They are easy (once you know which tools to use), and I cannot expect that these proofs will give insight into how to solve the case being asked: with a gap, pairwise bounded, $\Omega(n^2)$ clauses.  My guess is that the case being asked requires a very different idea from these cases.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-02T15:53:44.230Z
Just noting the obvious for others: pairwise $B$-bounded implies that there are $O(n^2)$ clauses; the additional requirement that there are at least $an^2$ clauses means that there must be $\Theta(n^2)$ clauses.  So it is possible that this version of the problem is less difficult, as the special structure of the clauses in this case might be enough for intermediate complexity, UGC-equivalence, or even polynomial-time.
András Salamon
<cc.complexity-theory><sat><approximation-hardness>
Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?
Tsuyoshi Ito
# Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

(Asked by: username_0 on 2010-09-26)

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*1∨*x*2∨*x*4)∧(￢*x*1∨￢*x*3∨*x*4)∧(*x*1∨*x*3∨￢*x*5) is pairwise 2-bounded but not pairwise 1-bounded because e.g. the pair (*x*1, *x*4) 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*2 clauses, where *n* is the number of variables?

The pairwise boundedness clearly implies that there are only O(*n*2) 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*3) 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)](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aM#mipstar21) 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>

**Tags:** cc.complexity-theory, sat, approximation-hardness

> **Comments:**
> **username_3**: @Tsuyoshi: am I right in presuming that nothing is known about the other intermediate cases, between $m = O(n)$ and $m = \Omega(n^3)$?  
> **username_0**: @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](http://dx.doi.org/10.1016/j.ic.2007.02.006). The proof of (3) uses expanders.  
> **username_3**: @Tsuyoshi: Looking forward to reading your paper.  
> **username_0**: @András: Uh-oh.  Currently I have no plan to write up a paper from these results.  They are easy (once you know which tools to use), and I cannot expect that these proofs will give insight into how to solve the case being asked: with a gap, pairwise bounded, $\Omega(n^2)$ clauses.  My guess is that the case being asked requires a very different idea from these cases.  
> **username_3**: Just noting the obvious for others: pairwise $B$-bounded implies that there are $O(n^2)$ clauses; the additional requirement that there are at least $an^2$ clauses means that there must be $\Theta(n^2)$ clauses.  So it is possible that this version of the problem is less difficult, as the special structure of the clauses in this case might be enough for intermediate complexity, UGC-equivalence, or even polynomial-time.  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: The link to the Complexity Zoo must have been broken for a long time!  Sorry for bumping the question without any update in the content.  

---

## 1 answers

### Answer by username_4 on 2011-09-04. Score: 6

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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: @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.  
> **username_4**: 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.  
> **username_0**: 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!  
> **username_4**: No problem. Glad I could be of help.  

---

