# Solving $n$-SAT and #$n$-SAT

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)

• $k$-SAT allows for more than $k$ variables. You appear to only give special cases of $k$-SAT. – Timothy Sun Aug 27 '11 at 1:07
• 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 Aug 27 '11 at 1:13
• @RyanWilliams sounds like an answer to me :) – Suresh Venkat Aug 27 '11 at 3:14
• 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 Aug 27 '11 at 10:21
• @AndrasSalamon : Right. Is it a proof of non #P-completness ? – Xavier Labouze Aug 27 '11 at 19:58

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$!
• #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 Aug 27 '11 at 18:28
• What is the reduction from $k$-SAT to $(k+1)$-SAT on the same $n$ variables? – Timothy Sun Aug 27 '11 at 20:06