<p>I don't know the answer to your specific question (it seems related to the question of whether W<a href="https://scholar.google.com/scholar?biw=1895&amp;bih=878&amp;bav=on.2,or.r_cp.&amp;bvm=bv.117218890,d.cGc&amp;um=1&amp;ie=UTF-8&amp;lr&amp;cites=11230959911679679574" rel="nofollow">1</a>=W[2]). </p>

<p>But the algorithm you give in your question is subsumed by several other results. Using your definition of $N$, CNF-SAT is basically solvable in $O(1.1279^N)$ time, as in the <a href="https://scholar.google.com/scholar?biw=1895&amp;bih=878&amp;bav=on.2,or.r_cp.&amp;bvm=bv.117218890,d.cGc&amp;um=1&amp;ie=UTF-8&amp;lr&amp;cites=11230959911679679574" rel="nofollow">paper by Wahlstrom</a> (link goes to a google scholar page of papers that cite it). In particular, Wahlstrom shows that if $d$ is the average number of occurrences of a variable in the CNF, and no variable appears at most once, then CNF-SAT can be solved in $O(1.1279^{n(d - 2)})$ time. (There are other references with similarly strong running times.)</p>

<p>Update: Another reference is: </p>

<p>Hirsch, E.A.: New worst-case upper bounds for SAT. J. Autom.
Reason. 24(4), 397–420 (2000)</p>

<p>This gives faster algorithms in terms of $m$ and your $N$ (which is typically called $\ell$). Namely, Hirsch gets $2^{0.30897m}$ and $2^{0.10299\ell}$ time.</p>

CC BY-SA 3.0
2016-03-21T01:34:36.703Z
Thank you very much for the link.  I appreciate it!  Also, I think your suggestion that it may be related to W[1] vs W[2] is a good insight.  By the way, can we solve CNF-SAT in $poly(N) \cdot 2^{(1-\epsilon) \cdot m}$ time?
Michael Wehar
CC BY-SA 3.0
2016-03-21T06:54:36.300Z
Yes, you can combine backtracking and dynamic programming to solve the problem in about $1.8^m$ time.
Ryan Williams
CC BY-SA 3.0
2016-04-09T17:40:56.130Z
After reading more, it seems that this question is related to M[1] vs W[2].  I'm still trying to learn more about the M hierarchy, but it's worth noting that M[1] $\subseteq$ W[1].  One relevant source to look at is "A Basic Parameterized Complexity Primer".  Please feel free to suggest more references that discuss the M hierarchy.
Michael Wehar
CC BY-SA 3.0
2016-03-20T16:31:10.937Z
2016-03-22T21:20:54.427Z
2016-03-22T21:20:54.427Z
Ryan Williams
<blockquote>
  <p>CNF-SAT refers to the following problem:</p>
  
  <p>Given a boolean formula $\phi$ in conjunctive normal form, does there
  exist an assignment to the variables that satisfies $\phi$.</p>
</blockquote>

<p>There are several parameters that one can associate with $\phi$:</p>

<ul>
<li>$n$ will denote the number of variables in $\phi$.</li>
<li>$m$ will denote the number of clauses in $\phi$.</li>
<li>$N$ will denote the number of variable occurrences in $\phi$.</li>
</ul>

<blockquote>
  <p><strong>Claim:</strong> For every fixed $k$, we can reduce an arbitrary instance $\phi$ of CNF-SAT to an instance $G$ of $k$-Clique with roughly
  $2^{\frac{N}{k}}$ vertices and $2^{\frac{2 N}{k}}$ edges.</p>
  
  <p><strong>Proof Idea:</strong> Any clause in $\phi$ can be split into two clauses by adding an
  additional variable.  The positive literal gets added to one of the
  new clauses and the negative literal gets added to the other new clause.</p>
  
  <p>We make at most $k$ splits to the clauses of $\phi$ to get a new
  formula $\phi'$ such that:</p>
  
  <ul>
  <li>$\phi'$ has at most $N+2k$ variable occurrences.</li>
  <li>$\phi'$ can be expressed as $\bigwedge_{i\in[k]} \phi_{i}'$ where each $\phi_{i}'$ is a CNF formula with at most $\frac{N}{k} + 2$
  variable occurrences.</li>
  <li>$\phi$ is satisfiable if and only if $\phi'$ is satisfiable.</li>
  </ul>
  
  <p>We can look at each $\phi_{i}'$ independently and build up a list of
  all the satisfying assignments.  There are at most $2^{\frac{N}{k}+2}$
  satisfying assignments for each $\phi_{i}'$.</p>
  
  <p>The satisfying assignments for the $\phi_i'$'s will represent the
  vertices of the graph $G$.  In total, $G$ will have at most $k \cdot 2^{\frac{N}{k}+2}$ vertices.</p>
  
  <p>Vertices $v$ and $u$ are adjacent in $G$ if the following are true:</p>
  
  <ul>
  <li>$v$ and $u$ represent assignments for $\phi_i'$ and $\phi_j'$ respectively where $i \neq j$.</li>
  <li>For the variables that are in both $\phi_i'$ and $\phi_j'$, the assignments for $v$ and $u$ agree on their respective bit values.</li>
  </ul>
  
  <p>Now, if a $k$-Clique exists in $G$, then we get an assignment for each
  $\phi_i'$ where no two assignments disagree on bit values for the same
  variables.  As a result, these assignments can be joined to form a
  satisfying assignment for $\phi'$.</p>
  
  <p>Conversely, if a satisfying assignment exists for $\phi'$, then we can
  remove variables from this assignment to get a satsfying assignment
  for each of the $\phi_i'$'s where no two assignments have any bit
  mismatches making them form a $k$-Clique in $G$.  $\square$</p>
</blockquote>

<p>Using fast matrix multiplication, we can solve $k$-Clique in $O(n^{.792 k})$ time.  Therefore, we can solve CNF-SAT in $2^{.792 N}$ time.  In fact, there is a trivial algorithm for solving CNF-SAT in $2^{.5 N}$ time.</p>

<p>However, it is not known if we can solve CNF-SAT in $poly(N) \cdot 2^{(1-\epsilon) \cdot n}$ time.</p>

<p><strong>Question:</strong> Does there exist a constant $c$ such that for every fixed $k$, we can reduce an arbitrary instance $\phi$ of CNF-SAT to an instance $G$ of $k$-Clique with roughly $2^{\frac{c \cdot n}{k}}$ vertices and $2^{\frac{2 \cdot c \cdot n}{k}}$ edges.</p>

<p><strong>Relevant Links:</strong></p>

<ul>
<li><p>Exponential Time Hypothesis: <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="noreferrer">https://en.wikipedia.org/wiki/Exponential_time_hypothesis</a></p></li>
<li><p>Algorithms for $k$-Clique: <a href="http://theory.stanford.edu/~virgi/combclique-ipl-g.pdf" rel="noreferrer">http://theory.stanford.edu/~virgi/combclique-ipl-g.pdf</a></p></li>
<li><p>Sparsification Lemma: <a href="https://cseweb.ucsd.edu/~russell/ipz.pdf" rel="noreferrer">https://cseweb.ucsd.edu/~russell/ipz.pdf</a></p></li>
</ul>

CC BY-SA 3.0
2016-03-19T15:26:53.303Z
@RickyDemer Thanks for the question.  The quantifiers are as follows: $\exists c \, \forall k \, \forall \alpha$
Michael Wehar
CC BY-SA 3.0
2016-03-19T17:56:02.083Z
**Note:** There is a trivial algorithm for solving CNF-SAT in $2^{.5 N}$ time.  If a variable only occurs once in $\phi$, then we can simply pick the bit value that satisfies the clause it is in to reduce the size of $\phi$.  After removing all of the single occurence variables, we get a reduced formula $\phi'$ with at most $\frac{N}{2}$ variables.  Then, we can try all assignments to solve satisfiability in $2^{\frac{N}{2}}$ time.
Michael Wehar
CC BY-SA 3.0
2016-03-20T22:10:49.367Z
Is N the quantity that is usually referred to as the number of literals?
András Salamon
CC BY-SA 3.0
2016-03-21T01:32:15.907Z
@AndrásSalamon I think you are right that $N$ is usually referred to as the number of literals, but that wording seems a little ambiguous.  This is because the number of possible literals is $2n$, but we mean literal occurrences which could be much more.
Michael Wehar
CC BY-SA 3.0
2016-03-23T19:44:39.720Z
Note that if you are parameterizing by $n$ rather than instance size, then there is a trivial $n.2^n$ time lower bound, since the $n$-variable instances containing only non-repeated full clauses (in which every variable occurs once) require at least this much time just to read the input, in the worst case of the unique unsatisfiable such formula.  So some care is required in the precise formulation.
András Salamon
CC BY-SA 3.0
2016-03-24T02:17:40.160Z
@AndrásSalamon That is a good observation!  Thank you.  :)
Michael Wehar
<np-hardness><sat><reductions><clique><fine-grained>
On reducing the hardness of CNF-SAT to k-Clique
Michael Wehar
# On reducing the hardness of CNF-SAT to k-Clique

(Asked by: username_0 on 2016-03-19)

> CNF-SAT refers to the following problem:
>
> Given a boolean formula $\phi$ in conjunctive normal form, does there
> exist an assignment to the variables that satisfies $\phi$.

There are several parameters that one can associate with $\phi$:

* $n$ will denote the number of variables in $\phi$.
* $m$ will denote the number of clauses in $\phi$.
* $N$ will denote the number of variable occurrences in $\phi$.

> **Claim:** For every fixed $k$, we can reduce an arbitrary instance $\phi$ of CNF-SAT to an instance $G$ of $k$-Clique with roughly
> $2^{\frac{N}{k}}$ vertices and $2^{\frac{2 N}{k}}$ edges.
>
> **Proof Idea:** Any clause in $\phi$ can be split into two clauses by adding an
> additional variable. The positive literal gets added to one of the
> new clauses and the negative literal gets added to the other new clause.
>
> We make at most $k$ splits to the clauses of $\phi$ to get a new
> formula $\phi'$ such that:
>
> * $\phi'$ has at most $N+2k$ variable occurrences.
> * $\phi'$ can be expressed as $\bigwedge\_{i\in[k]} \phi\_{i}'$ where each $\phi\_{i}'$ is a CNF formula with at most $\frac{N}{k} + 2$
>   variable occurrences.
> * $\phi$ is satisfiable if and only if $\phi'$ is satisfiable.
>
> We can look at each $\phi\_{i}'$ independently and build up a list of
> all the satisfying assignments. There are at most $2^{\frac{N}{k}+2}$
> satisfying assignments for each $\phi\_{i}'$.
>
> The satisfying assignments for the $\phi\_i'$'s will represent the
> vertices of the graph $G$. In total, $G$ will have at most $k \cdot 2^{\frac{N}{k}+2}$ vertices.
>
> Vertices $v$ and $u$ are adjacent in $G$ if the following are true:
>
> * $v$ and $u$ represent assignments for $\phi\_i'$ and $\phi\_j'$ respectively where $i \neq j$.
> * For the variables that are in both $\phi\_i'$ and $\phi\_j'$, the assignments for $v$ and $u$ agree on their respective bit values.
>
> Now, if a $k$-Clique exists in $G$, then we get an assignment for each
> $\phi\_i'$ where no two assignments disagree on bit values for the same
> variables. As a result, these assignments can be joined to form a
> satisfying assignment for $\phi'$.
>
> Conversely, if a satisfying assignment exists for $\phi'$, then we can
> remove variables from this assignment to get a satsfying assignment
> for each of the $\phi\_i'$'s where no two assignments have any bit
> mismatches making them form a $k$-Clique in $G$. $\square$

Using fast matrix multiplication, we can solve $k$-Clique in $O(n^{.792 k})$ time. Therefore, we can solve CNF-SAT in $2^{.792 N}$ time. In fact, there is a trivial algorithm for solving CNF-SAT in $2^{.5 N}$ time.

However, it is not known if we can solve CNF-SAT in $poly(N) \cdot 2^{(1-\epsilon) \cdot n}$ time.

**Question:** Does there exist a constant $c$ such that for every fixed $k$, we can reduce an arbitrary instance $\phi$ of CNF-SAT to an instance $G$ of $k$-Clique with roughly $2^{\frac{c \cdot n}{k}}$ vertices and $2^{\frac{2 \cdot c \cdot n}{k}}$ edges.

**Relevant Links:**

* Exponential Time Hypothesis: <https://en.wikipedia.org/wiki/Exponential_time_hypothesis>
* Algorithms for $k$-Clique: <http://theory.stanford.edu/~virgi/combclique-ipl-g.pdf>
* Sparsification Lemma: <https://cseweb.ucsd.edu/~russell/ipz.pdf>

**Tags:** np-hardness, sat, reductions, clique, fine-grained
> **Comments:**
> **username_0**: @RickyDemer Thanks for the question.  The quantifiers are as follows: $\exists c \, \forall k \, \forall \alpha$  
> **username_0**: **Note:** There is a trivial algorithm for solving CNF-SAT in $2^{.5 N}$ time.  If a variable only occurs once in $\phi$, then we can simply pick the bit value that satisfies the clause it is in to reduce the size of $\phi$.  After removing all of the single occurence variables, we get a reduced formula $\phi'$ with at most $\frac{N}{2}$ variables.  Then, we can try all assignments to solve satisfiability in $2^{\frac{N}{2}}$ time.  
> **username_1**: Is N the quantity that is usually referred to as the number of literals?  
> **username_0**: @AndrásSalamon I think you are right that $N$ is usually referred to as the number of literals, but that wording seems a little ambiguous.  This is because the number of possible literals is $2n$, but we mean literal occurrences which could be much more.  
> **username_1**: Note that if you are parameterizing by $n$ rather than instance size, then there is a trivial $n.2^n$ time lower bound, since the $n$-variable instances containing only non-repeated full clauses (in which every variable occurs once) require at least this much time just to read the input, in the worst case of the unique unsatisfiable such formula.  So some care is required in the precise formulation.  
> **username_0**: @AndrásSalamon That is a good observation!  Thank you.  :)  

---

## 1 answers

### Answer by username_2 on 2016-03-20. Score: 11

I don't know the answer to your specific question (it seems related to the question of whether W[1](https://scholar.google.com/scholar?biw=1895&bih=878&bav=on.2,or.r_cp.&bvm=bv.117218890,d.cGc&um=1&ie=UTF-8&lr&cites=11230959911679679574)=W[2]).

But the algorithm you give in your question is subsumed by several other results. Using your definition of $N$, CNF-SAT is basically solvable in $O(1.1279^N)$ time, as in the [paper by Wahlstrom](https://scholar.google.com/scholar?biw=1895&bih=878&bav=on.2,or.r_cp.&bvm=bv.117218890,d.cGc&um=1&ie=UTF-8&lr&cites=11230959911679679574) (link goes to a google scholar page of papers that cite it). In particular, Wahlstrom shows that if $d$ is the average number of occurrences of a variable in the CNF, and no variable appears at most once, then CNF-SAT can be solved in $O(1.1279^{n(d - 2)})$ time. (There are other references with similarly strong running times.)

Update: Another reference is:

Hirsch, E.A.: New worst-case upper bounds for SAT. J. Autom.
Reason. 24(4), 397–420 (2000)

This gives faster algorithms in terms of $m$ and your $N$ (which is typically called $\ell$). Namely, Hirsch gets $2^{0.30897m}$ and $2^{0.10299\ell}$ time.

> **Comments:**
> **username_0**: Thank you very much for the link.  I appreciate it!  Also, I think your suggestion that it may be related to W[1] vs W[2] is a good insight.  By the way, can we solve CNF-SAT in $poly(N) \cdot 2^{(1-\epsilon) \cdot m}$ time?  
> **username_2**: Yes, you can combine backtracking and dynamic programming to solve the problem in about $1.8^m$ time.  
> **username_0**: After reading more, it seems that this question is related to M[1] vs W[2].  I'm still trying to learn more about the M hierarchy, but it's worth noting that M[1] $\subseteq$ W[1].  One relevant source to look at is "A Basic Parameterized Complexity Primer".  Please feel free to suggest more references that discuss the M hierarchy.  

---

