-2
$\begingroup$

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)

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

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$!

$\endgroup$
15
  • $\begingroup$ 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 ? $\endgroup$ Aug 27 '11 at 9:31
  • $\begingroup$ I believe a reduction from #2-SAT is possible. $\endgroup$ Aug 27 '11 at 15:15
  • 1
    $\begingroup$ #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). $\endgroup$ Aug 27 '11 at 18:28
  • $\begingroup$ 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) ? $\endgroup$ Aug 27 '11 at 19:19
  • $\begingroup$ What is the reduction from $k$-SAT to $(k+1)$-SAT on the same $n$ variables? $\endgroup$ Aug 27 '11 at 20:06

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.