<p>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).</p>

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

CC BY-SA 3.0
2011-10-11T07:39:05.907Z
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 ?)
Xavier Labouze
CC BY-SA 3.0
2011-10-11T16:56:32.133Z
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.
Noam
CC BY-SA 3.0
2011-10-12T22:27:59.473Z
$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 ?
Xavier Labouze
CC BY-SA 3.0
2011-10-15T00:48:39.647Z
$F'$ is exponential in size of $F$ (if $m$ is exponential in $|F|$), thus the reduction is not poly-time in general.
Opt
CC BY-SA 3.0
2011-10-09T19:08:48.653Z
2011-10-09T19:08:48.653Z
Noam
<p>Unique SAT is the well known problem : given a CNF formula $F$, is it true that $F$ has exactly one model ?</p>

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

<p>Both problems look similar. So my questions are : </p>

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

<p>2- Do you know any reference on the subject ? </p>

<p>Thank you for your answers.</p>

<p><strong>Addendum</strong>, first articles about complexity of Exactly $m$ SAT :</p>

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

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

<p>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$".</p>

CC BY-SA 3.0
2011-09-27T06:06:27.420Z
It is polytime Turing reducible: find a solution, add a clause eliminating it, and repeat till the formula becomes unsatisfiable.
Kaveh
CC BY-SA 3.0
2011-09-27T12:17:52.470Z
@Kaveh ,Tks. 1- what if the initial formula hasn't exactly m models ? (possibly exactly one); 2- how to be sure that the added clause eliminates no more than one solution ? (then we would have to test the values of m'<m)
Xavier Labouze
CC BY-SA 3.0
2011-09-27T21:05:04.800Z
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.
Kaveh
CC BY-SA 3.0
2011-09-27T21:40:45.973Z
@Kaveh, 1. I meant what if the machine gives a no answer to the Exactly $m$ SAT problem ?  (we don't have access to the number of solutions, $m$ is given) 2. Nice !
Xavier Labouze
CC BY-SA 3.0
2011-09-28T05:04:16.723Z
(I should cut and paste this :)): answers, not comments...
Suresh Venkat
CC BY-SA 3.0
2011-09-29T23:56:44.183Z
@Kaveh: I do not think that your reduction works unless m is polynomially bounded in the input size.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T00:27:52.660Z
@Kaveh: I realized that I cannot understand your reduction even for m=2.  How can you use the oracle for Unique SAT to find a solution for a SAT instance with two answers?  Are you using the randomized reduction by Valiant and Vazirani?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T11:47:58.737Z
@Tsuyoshi, you are right, I misunderstood the question.
Kaveh
CC BY-SA 3.0
2011-09-30T12:25:47.663Z
@Xavier: I cannot see how to solve “Exactly m SAT” by using the NP oracle twice.  Care to elaborate?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T12:52:39.523Z
@Tsuyoshi: It is the same kind of oracle calls for US and "Exactly $m$ models" :  First NP call : Has the formula more or equal $m$ models ? Second co-NP call : Has the formula stricly less than $m+1$ models ?
Xavier Labouze
CC BY-SA 3.0
2011-09-30T13:25:37.020Z
What if m is exponentially large in the input size?  I think that you are using the PP oracle twice.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T13:44:04.277Z
@Tsuyoshi: 1- Why is it necessary to introduce probalistic TM even if $m$ is exponentially large in the input size ? 2- Let $m$ be small enough, the question of reducibility from "Exactly $m$ SAT" to US remains.
Xavier Labouze
CC BY-SA 3.0
2011-09-30T13:51:35.903Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T13:55:25.117Z
Also, please make an effort to state your question precisely, and update the question so that people can understand your question without reading comments.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T15:01:32.063Z
Well, if you think that your questions are too naive, I have to agree.  Honestly speaking, I think that you should have asked your questions on math.stackexchange.com instead of cstheory.stackexchange.com.  They are by no means research-level questions in complexity theory.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T21:33:42.583Z
@Tsuyoshi : Tks for the link (naive questions do have virtues, I learnt this from my students).
Xavier Labouze
CC BY-SA 3.0
2011-09-30T23:51:01.057Z
@Tayfun,about your comment :-) - What else do you think about the posted question ?
Xavier Labouze
CC BY-SA 3.0
2011-10-02T23:37:51.447Z
(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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-03T07:28:37.153Z
@Tsuyoshi : (1) This reduction maps yes instances, what about no instances ? (2) tks for your concern.
Xavier Labouze
CC BY-SA 3.0
2011-10-03T13:04:17.940Z
It maps no-instances to no-instances (otherwise I would not call it a reduction).
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-05T12:36:16.743Z
@Tsuyoshi : Please make your answering comment a full answer.
Xavier Labouze
CC BY-SA 3.0
2011-10-08T13:05:48.507Z
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.
Tsuyoshi Ito
<cc.complexity-theory><reference-request><np-hardness><sat><reductions>
Unique SAT vs Exactly $m$ models
Xavier Labouze
# Unique SAT vs Exactly $m$ models

(Asked by: username_0 on 2011-09-26)

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$".

**Tags:** cc.complexity-theory, reference-request, np-hardness, sat, reductions
> **Comments:**
> **username_1**: It is polytime Turing reducible: find a solution, add a clause eliminating it, and repeat till the formula becomes unsatisfiable.  
> **username_0**: @Kaveh ,Tks. 1- what if the initial formula hasn't exactly m models ? (possibly exactly one); 2- how to be sure that the added clause eliminates no more than one solution ? (then we would have to test the values of m'<m)  
> **username_1**: 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.  
> **username_0**: @Kaveh, 1. I meant what if the machine gives a no answer to the Exactly $m$ SAT problem ?  (we don't have access to the number of solutions, $m$ is given) 2. Nice !  
> **username_2**: (I should cut and paste this :)): answers, not comments...  
> **username_3**: @Kaveh: I do not think that your reduction works unless m is polynomially bounded in the input size.  
> **username_3**: @Kaveh: I realized that I cannot understand your reduction even for m=2.  How can you use the oracle for Unique SAT to find a solution for a SAT instance with two answers?  Are you using the randomized reduction by Valiant and Vazirani?  
> **username_1**: @Tsuyoshi, you are right, I misunderstood the question.  
> **username_3**: @Xavier: I cannot see how to solve “Exactly m SAT” by using the NP oracle twice.  Care to elaborate?  
> **username_0**: @Tsuyoshi: It is the same kind of oracle calls for US and "Exactly $m$ models" :  First NP call : Has the formula more or equal $m$ models ? Second co-NP call : Has the formula stricly less than $m+1$ models ?  
> **username_3**: What if m is exponentially large in the input size?  I think that you are using the PP oracle twice.  
> **username_0**: @Tsuyoshi: 1- Why is it necessary to introduce probalistic TM even if $m$ is exponentially large in the input size ? 2- Let $m$ be small enough, the question of reducibility from "Exactly $m$ SAT" to US remains.  
> **username_3**: 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.  
> **username_3**: Also, please make an effort to state your question precisely, and update the question so that people can understand your question without reading comments.  
> **username_3**: Well, if you think that your questions are too naive, I have to agree.  Honestly speaking, I think that you should have asked your questions on math.stackexchange.com instead of cstheory.stackexchange.com.  They are by no means research-level questions in complexity theory.  
> **username_0**: @Tsuyoshi : Tks for the link (naive questions do have virtues, I learnt this from my students).  
> **username_0**: @Tayfun,about your comment :-) - What else do you think about the posted question ?  
> **username_3**: (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.  
> **username_0**: @Tsuyoshi : (1) This reduction maps yes instances, what about no instances ? (2) tks for your concern.  
> **username_3**: It maps no-instances to no-instances (otherwise I would not call it a reduction).  
> **username_0**: @Tsuyoshi : Please make your answering comment a full answer.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2011-10-09. Score: 13 | Accepted answer

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.

> **Comments:**
> **username_0**: 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 ?)  
> **username_4**: 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.  
> **username_0**: $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 ?  
> **username_5**: $F'$ is exponential in size of $F$ (if $m$ is exponential in $|F|$), thus the reduction is not poly-time in general.  

---

