12
$\begingroup$

Unique SAT is the well known problem : given a CNF formula $F$, is it true that $F$ has exactly one model ?

I am interested in « Exactly $m$-SAT » problem : given a CNF formula $F$ and an integer $m>1$, is it true that $F$ has exactly $m$ models ?

Both problems look similar. So my questions are :

1- Is «Exactly $m$-SAT » polytime (many-one or Turing) reducible to Unique SAT?

2- Do you know any reference on the subject ?

Thank you for your answers.

Addendum, first articles about complexity of Exactly $m$ SAT :

1- Janos Simon, On the Difference Between One and Many, In Proceedings of the Fourth Colloquium on Automata, Languages and Programming, 480-491, 1977.

2- Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 23, 325-356, 1986.

In both articles, Exactly $m$ SAT ($m \geq 1$) is shown to be $C=$ complete (under many-one reductions), where the class $C$ is from the Counting Hierarchy (CH) of complexity classes. Informally, $C$ contains all problems which can be expressed as deciding whether a given instance has at least $m$ many polynomial size proofs (the class $C$ is known to coincide with the class $PP$). The class $C=$ is a variant of $C$, where “exactly $m$” replaces “at least $m$".

Improve this question
$\endgroup$
22
  • 4
    $\begingroup$ It is polytime Turing reducible: find a solution, add a clause eliminating it, and repeat till the formula becomes unsatisfiable. $\endgroup$
    – Kaveh
    Commented Sep 27, 2011 at 6:06
  • 1
    $\begingroup$ 1. the machine will tell the number of solutions or that it has more than $m$ solutions. 2. you can add the negation of conjunction describing the solution. $\endgroup$
    – Kaveh
    Commented Sep 27, 2011 at 21:05
  • 1
    $\begingroup$ If you do not know the relation between PP and counting the number of solutions, please check a textbook on complexity theory such as Papadimitriou. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 30, 2011 at 13:51
  • 6
    $\begingroup$ (1) If m is polynomially bounded, your problem is polynomial-time many-one reducible to Unique SAT by treating a list of m solutions sorted in the lexicographical order as a single certificate. (2) Please do not take my giving an answer as an evidence that you asked your question in the right place. I think that this particular question is on the border line between on-topic and off-topic. You should really consider asking your future questions somewhere else. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 2, 2011 at 23:37
  • 4
    $\begingroup$ Although you state that m is polynomially bounded, some of the statements in the question require m to be arbitrary and no longer hold if you constrain m to be polynomially bounded. You have to understand what you are talking about before you can ask a coherent question. This is why I do not want to post an answer to this question here, where questions are expected to be at research level. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 8, 2011 at 13:05

1 Answer 1

Reset to default
13
$\begingroup$

For general $m$, exactly-m-sat is strictly harder than u-sat (thus does not reduce to it) unless the PH collapses. The reason is that PP can be obtained using an existential quantifier over exactly-m-SAT queries (exists m>(half of the assignments) such that exactly-m-SAT), thus if exactly-m-sat is in the k'th level of PH, then PP is in the (k+1)'st level, and then the hierarchy collapses (since P^PP contains PH). But u-sat is clearly in the second level of PH (actually in a subclass called DP).

On the other hand, as @Tsuyoshi mentioned above, if $m$ is polynomial, then exactly-m-sat is many-one reudcible to u-sat.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your answer. 1) If $m$ is small enough (ie polynomially bounded in $n$, the size of the formula) then Exactly $m$ SAT is reducible to US. Besides, if $m$, as part of the input, is big enough (ie $m= 2^{O(n)}$) then Exactly $m$ SAT is in P. Why would it be such a drastic change for $m$ in between ? 2) What do you think of the update post ? (why is it not correct ?) $\endgroup$
    – Xavier Labouze
    Commented Oct 11, 2011 at 7:39
  • $\begingroup$ Large m still don't put the problem in P. The update post is incorrect since the statement that exactly-k-sat is C=P-complete is true when k is part of the input, and thus your reduction to k/2-sat does not make sense. $\endgroup$
    – Noam
    Commented Oct 11, 2011 at 16:56
  • $\begingroup$ $m$ is part of the input. Let introduce $m$ new variables, $y_1,y_2 \cdots y_m $. Let $F'=F\land y_1 \land y_2 \land \cdots \land y_m $. $F'$ has exactly the same number of models as $F$, and $m$ is polynomially bound in the size of $F'$. Why not conclude that the reduction to US (via $F'$) holds ? $\endgroup$
    – Xavier Labouze
    Commented Oct 12, 2011 at 22:27
  • 1
    $\begingroup$ $F'$ is exponential in size of $F$ (if $m$ is exponential in $|F|$), thus the reduction is not poly-time in general. $\endgroup$
    – Opt
    Commented Oct 15, 2011 at 0:48

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.