<p>Your "n-SAT" problem is just asking if all possible $2^n$ clauses are present. For this problem to be $NP$-complete, you would have to be able to reduce unsatisfiable instances of SAT to polynomial size unsatisfiable instances of this problem.</p>

<p>But an instance of "n-SAT" is only unsatisfiable when the number of variables is at most $\log N$, where $N$ is the input length (analogously, when the number of clauses is at least $2^n$, where $n$ is the number of variables). So your polynomial time reduction would have to decrease the number of variables from $N$ to logarithmic in $N$... good luck!</p>

<p><strong>UPDATE:</strong> You ask why your set <em>isn't</em> NP-complete. Note that this is a loaded question. Your set is in $P$, as established earlier. If $P=NP$ then <em>every</em> nontrivial set $S$ that's in $P$ is actually $NP$-complete (nontrivial means: there is at least one string $x \in S$ and one string $y \notin S$). If $P=NP$ we have a polytime SAT algorithm. To reduce SAT to $S$, just call the SAT algorithm and output $x$ if your SAT algorithm says "yes", $y$ if it says "no". So to <em>prove</em> to you that your $S \in P$ <em>cannot</em> be $NP$-complete is tantamount to proving $P \neq NP$! </p>

CC BY-SA 3.0
2011-09-01T14:58:23.977Z
@RyanWilliams : tks for your uptade which makes definitively clearer to me the issue.
Xavier Labouze
CC BY-SA 3.0
2011-08-27T09:31:30.293Z
Tks for your answer. I understand that "just asking if all possible clauses are present" cannot be NP-complete. That means that this n-SAT problem cannot be so. That is also true for (n-1)-SAT problem, and by recurrence, for any k≤n like k = 3. What to think then ? And what to answer to the #n-SAT part of the first question ?
Xavier Labouze
CC BY-SA 3.0
2011-08-27T15:15:28.127Z
I believe a reduction from #2-SAT is possible.
Timothy Sun
CC BY-SA 3.0
2011-08-27T18:28:09.913Z
#2-SAT is #P-complete, which reduces to any #$k$-SAT fairly trivially. However, your problem does not seem to be #P-complete (see Andras's comment).
Timothy Sun
CC BY-SA 3.0
2011-08-27T19:19:40.767Z
But what about the polynomial reduction from k-SAT on n variables to (k+1)-SAT on the same n variables? How can the recurrence stop before reaching the ultimate possible k (which is n) ?
Xavier Labouze
CC BY-SA 3.0
2011-08-27T20:06:12.257Z
What is the reduction from $k$-SAT to $(k+1)$-SAT on the same $n$ variables?
Timothy Sun
CC BY-SA 3.0
2011-08-27T22:18:25.910Z
@TimothySun : Each k-clause is transformed in a conjunction of two (k+1) clauses by adding a missing variable in one clause and its negation in the other.
Xavier Labouze
CC BY-SA 3.0
2011-08-27T22:31:39.043Z
Oh okay. But your definition of "2-SAT" is not 2-SAT.
Timothy Sun
CC BY-SA 3.0
2011-08-28T22:38:03.783Z
@TimothySun : Sorry to keep asking, but what is the problem with the definition of k-SAT ?
Xavier Labouze
CC BY-SA 3.0
2011-08-28T22:41:54.383Z
You can have more than $k$ variables in $k$-SAT.
Timothy Sun
CC BY-SA 3.0
2011-08-28T23:30:11.343Z
@TimothySun : Of course. Does it mean that _k_ -SAT on _n_ variables is not NP-complete ?
Xavier Labouze
CC BY-SA 3.0
2011-08-29T03:27:49.987Z
$k$-SAT for $k \geq 3$ is NP-complete.
Timothy Sun
CC BY-SA 3.0
2011-08-29T11:07:59.633Z
@TimothySun : Of course, and k-SAT on n variables is still NP-complete, and k-SAT on n variables is reducible to (K+1)-SAT on n variables, and the question of understanding where (and how) the recurrence stops remains.
Xavier Labouze
CC BY-SA 3.0
2011-08-29T13:04:50.903Z
Oh, I misread what you wrote earlier. $k$-SAT on $n$ variables is not NP-complete because the language is (more or less) finite.
Timothy Sun
CC BY-SA 3.0
2011-08-29T13:05:28.377Z
Also, your polytime reduction goes from a problem in P to another problem in P.
Timothy Sun
CC BY-SA 3.0
2011-08-27T08:29:46.543Z
2011-09-01T09:32:12.440Z
2011-09-01T09:32:12.440Z
Ryan Williams
<p>Let $F$ be an $n$–SAT formula on $n$ variables (ie a CNF formula containing exclusively total clauses, with all variables in each), and let $c$ be the number of different clauses in $F$ ($c \le 2^n$).</p>

<p>It is immediate that $F$ is satisfiable iff $c&#160;&lt;&#160;2^n$.
It is also easy to show that the number $m$ of models of $F$ is equal to  $2^n - c$. </p>

<p>My questions are then:</p>

<p>Why #$n$-SAT on $n$ variables is not #P-complete? (Why $n$-SAT on $n$ variables is not NP-complete? - Edit : This question has been answered)</p>

CC BY-SA 3.0
2011-08-27T01:07:12.873Z
$k$-SAT allows for more than $k$ variables. You appear to only give special cases of $k$-SAT.
Timothy Sun
CC BY-SA 3.0
2011-08-27T01:13:23.800Z
Your "n-SAT" problem is just asking if all possible $2^n$ clauses are present. For this problem to be $NP$-complete, you would have to be able to reduce unsatisfiable instances of $SAT$ to *polynomial size* unsat instances of this problem. But an instance of "n-SAT" is only unsatisfiable when the number of variables is less than $\log N$, where $N$ is the input length. So your polynomial time reduction would have to decrease the number of variables from $N$ to logarithmic in $N$... good luck!
Ryan Williams
CC BY-SA 3.0
2011-08-27T03:14:14.960Z
@RyanWilliams sounds like an answer to me :)
Suresh Venkat
CC BY-SA 3.0
2011-08-27T10:21:32.673Z
A simpler way to think about "n-SAT" is that each $n$-variable clause forbids precisely one assignment to the $n$ variables.  Obviously there are $2^n$ possible assignments.
András Salamon
CC BY-SA 3.0
2011-08-27T19:58:34.527Z
@AndrasSalamon : Right. Is it a proof of non #P-completness ?
Xavier Labouze
<cc.complexity-theory><sat><counting-complexity>
Solving $n$-SAT and #$n$-SAT
Xavier Labouze
# Solving $n$-SAT and #$n$-SAT

(Asked by: username_0 on 2011-08-27)

Let $F$ be an $n$–SAT formula on $n$ variables (ie a CNF formula containing exclusively total clauses, with all variables in each), and let $c$ be the number of different clauses in $F$ ($c \le 2^n$).

It is immediate that $F$ is satisfiable iff $c < 2^n$.
It is also easy to show that the number $m$ of models of $F$ is equal to $2^n - c$.

My questions are then:

Why #$n$-SAT on $n$ variables is not #P-complete? (Why $n$-SAT on $n$ variables is not NP-complete? - Edit : This question has been answered)

**Tags:** cc.complexity-theory, sat, counting-complexity

> **Comments:**
> **username_1**: $k$-SAT allows for more than $k$ variables. You appear to only give special cases of $k$-SAT.  
> **username_2**: Your "n-SAT" problem is just asking if all possible $2^n$ clauses are present. For this problem to be $NP$-complete, you would have to be able to reduce unsatisfiable instances of $SAT$ to *polynomial size* unsat instances of this problem. But an instance of "n-SAT" is only unsatisfiable when the number of variables is less than $\log N$, where $N$ is the input length. So your polynomial time reduction would have to decrease the number of variables from $N$ to logarithmic in $N$... good luck!  
> **username_3**: @RyanWilliams sounds like an answer to me :)  
> **username_4**: A simpler way to think about "n-SAT" is that each $n$-variable clause forbids precisely one assignment to the $n$ variables.  Obviously there are $2^n$ possible assignments.  
> **username_0**: @AndrasSalamon : Right. Is it a proof of non #P-completness ?  

---

## 1 answers

### Answer by username_2 on 2011-08-27. Score: 12 | Accepted answer

Your "n-SAT" problem is just asking if all possible $2^n$ clauses are present. For this problem to be $NP$-complete, you would have to be able to reduce unsatisfiable instances of SAT to polynomial size unsatisfiable instances of this problem.

But an instance of "n-SAT" is only unsatisfiable when the number of variables is at most $\log N$, where $N$ is the input length (analogously, when the number of clauses is at least $2^n$, where $n$ is the number of variables). So your polynomial time reduction would have to decrease the number of variables from $N$ to logarithmic in $N$... good luck!

**UPDATE:** You ask why your set *isn't* NP-complete. Note that this is a loaded question. Your set is in $P$, as established earlier. If $P=NP$ then *every* nontrivial set $S$ that's in $P$ is actually $NP$-complete (nontrivial means: there is at least one string $x \in S$ and one string $y \notin S$). If $P=NP$ we have a polytime SAT algorithm. To reduce SAT to $S$, just call the SAT algorithm and output $x$ if your SAT algorithm says "yes", $y$ if it says "no". So to *prove* to you that your $S \in P$ *cannot* be $NP$-complete is tantamount to proving $P \neq NP$!

> **Comments:**
> **username_0**: Tks for your answer. I understand that "just asking if all possible clauses are present" cannot be NP-complete. That means that this n-SAT problem cannot be so. That is also true for (n-1)-SAT problem, and by recurrence, for any k≤n like k = 3. What to think then ? And what to answer to the #n-SAT part of the first question ?  
> **username_1**: I believe a reduction from #2-SAT is possible.  
> **username_1**: #2-SAT is #P-complete, which reduces to any #$k$-SAT fairly trivially. However, your problem does not seem to be #P-complete (see Andras's comment).  
> **username_0**: But what about the polynomial reduction from k-SAT on n variables to (k+1)-SAT on the same n variables? How can the recurrence stop before reaching the ultimate possible k (which is n) ?  
> **username_1**: What is the reduction from $k$-SAT to $(k+1)$-SAT on the same $n$ variables?  
> **username_0**: @TimothySun : Each k-clause is transformed in a conjunction of two (k+1) clauses by adding a missing variable in one clause and its negation in the other.  
> **username_1**: Oh okay. But your definition of "2-SAT" is not 2-SAT.  
> **username_0**: @TimothySun : Sorry to keep asking, but what is the problem with the definition of k-SAT ?  
> **username_1**: You can have more than $k$ variables in $k$-SAT.  
> **username_0**: @TimothySun : Of course. Does it mean that _k_ -SAT on _n_ variables is not NP-complete ?  
> **username_1**: $k$-SAT for $k \geq 3$ is NP-complete.  
> **username_0**: @TimothySun : Of course, and k-SAT on n variables is still NP-complete, and k-SAT on n variables is reducible to (K+1)-SAT on n variables, and the question of understanding where (and how) the recurrence stops remains.  
> **username_1**: Oh, I misread what you wrote earlier. $k$-SAT on $n$ variables is not NP-complete because the language is (more or less) finite.  
> **username_1**: Also, your polytime reduction goes from a problem in P to another problem in P.  
> **username_0**: @RyanWilliams : tks for your uptade which makes definitively clearer to me the issue.  

---

