-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)

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ $k$-SAT allows for more than $k$ variables. You appear to only give special cases of $k$-SAT. $\endgroup$
    – Timothy Sun
    Commented Aug 27, 2011 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$
    – Ryan Williams
    Commented Aug 27, 2011 at 1:13
  • 3
    $\begingroup$ @RyanWilliams sounds like an answer to me :) $\endgroup$
    – Suresh Venkat
    Commented Aug 27, 2011 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$
    – András Salamon
    Commented Aug 27, 2011 at 10:21
  • $\begingroup$ @AndrasSalamon : Right. Is it a proof of non #P-completness ? $\endgroup$
    – Xavier Labouze
    Commented Aug 27, 2011 at 19:58

1 Answer 1

Reset to default
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$!

Improve this answer
$\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$
    – Xavier Labouze
    Commented Aug 27, 2011 at 9:31
  • $\begingroup$ I believe a reduction from #2-SAT is possible. $\endgroup$
    – Timothy Sun
    Commented Aug 27, 2011 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$
    – Timothy Sun
    Commented Aug 27, 2011 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$
    – Xavier Labouze
    Commented Aug 27, 2011 at 19:19
  • $\begingroup$ What is the reduction from $k$-SAT to $(k+1)$-SAT on the same $n$ variables? $\endgroup$
    – Timothy Sun
    Commented Aug 27, 2011 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.