<p>Here's a small variation on the original question. Let $O$ be an oracle which, on input $(f_1,f_2)$ outputs 1 if CNF $f_1$ has <strong>more</strong> solutions than CNF $f_2$.</p>

<p>Given this oracle, we build a poly-time machine $M$ which can solve the #P-complete problem of computing the number of solutions to a given CNF $\varphi$. Note that that $\varphi$ can have an exponential number of solutions.</p>

<p>$M$ works as follows: It generates formulas with known number of solutions, and using binary search and by asking at most polynomial queries to $O$, it finds a formulas $\varphi_i$ which has <strong>the same</strong> number of solutions as $\varphi$. It finally outputs the number of solutions just found.</p>

<p>This shows that $M^O$ has complexity #P.</p>

CC BY-SA 2.5
2010-11-16T20:13:40.080Z
Forgive my ignorance, but how do you generate a formula with a pre-specified number of solutions?
Giorgio Camerani
CC BY-SA 2.5
2010-11-16T21:36:18.320Z
Let M be a (k+1)-bit number $M = \sum_{i=0}^k m_i 2^i$, and let $S$ be the indices $i$ where $m_i=1$. Make a formula with variables $x_0, \ldots, x_k$ and $y_0, \ldots, y_k$. For each $i \in S$, let $F_i$ be the following subformula: "All of $\{x_0,\ldots,x_{k-i}\}$ are true AND among $\{y_0, \ldots, y_k\}$ only $y_i$ is true." $F_i$ has $2^i$ satisfying assignments (the variables $\{x_{k-i+1}, \ldots, x_k\}$ are free), and for $i\ne j$, the satisfying assignments of $F_i$ and $F_j$ are disjoint due to the $y$ variables. The formula $\bigvee_{i\in S} F_i$ has $M$ satisfying assignments.
mikero
CC BY-SA 2.5
2010-11-17T02:56:41.550Z
Note that it is PP-complete to decide whether, given two CNF formulas f_1 and f_2, f_1 has more satisfying assignments than f_2 or not.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-17T10:38:32.397Z
@mikero: Ah, stupid me! I should have imagined that. Thanks for your illuminating explanation.
Giorgio Camerani
CC BY-SA 2.5
2010-11-16T19:32:12.423Z
2010-11-16T19:57:03.610Z
2010-11-16T19:57:03.610Z
Sadeq Dousti
<p>It seems like it's atleast NP-hard as one can easily construct a SAT formula with just one solution. Then by the Valiant-Vazirani theorem, there's a probabilistic reduction from every SAT formula to a set of Unique-SAT problems (determining whether a formula has a unique solution) and comparing those Unique-SAT problems with the constructed SAT formula with just one solution enables you to determine the satisfiability of the SAT formula under consideration.</p>

CC BY-SA 2.5
2010-11-17T03:41:20.717Z
To be precise, the first sentence should mention “under randomized reducibility” (although you mention it in the second sentence).
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-16T19:26:01.747Z
2010-11-16T19:26:01.747Z
Opt
<p>The problem is <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#conp">coNP</a>-hard; you can easily reduce the UNSAT problem to this problem.</p>

<p>A more precise characterization is that the problem is <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#cequalsp">C<sub>=</sub>P</a>-complete.  In fact, one definition of the class C<sub>=</sub>P is that it is the class of problems which are polynomial-time many-one reducible to this very problem (usually this definition is stated in terms of <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aG#gapp">GapP</a> functions).  But since this does not tell much, let me define this class in another way.</p>

<p>Let C<sub>=</sub>P be the class of problems which are polynomial-time many-one reducible to the following problem: given a boolean circuit <i>φ</i> and an integer <i>K</i> (in binary), decide whether the number of satisfying assignments of <i>φ</i> is equal to <i>K</i>.  By a standard reduction which shows the #P-completeness of #3SAT, we can restrict <i>φ</i> to be a 3CNF formula without affecting the class.  The class C<sub>=</sub>P contains a class called <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aU#us">US</a>, which contains both <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aU#up">UP</a> and coNP.</p>

<p>With this definition, your problem is C<sub>=</sub>P-complete.  Actually, the C<sub>=</sub>P-hardness is easy to see from the definition of the class C<sub>=</sub>P (which uses 3CNF formulas).</p>

<p>To prove the membership in C<sub>=</sub>P, suppose that we are to decide whether two given CNF formulas <i>φ</i><sub>1</sub> and <i>φ</i><sub>2</sub> have the same number of satisfying assignments or not.  Without loss of generality we can assume that the two formulas have the same number of variables, say <i>n</i>.  Construct a boolean circuit <i>φ</i> which takes <i>n</i>+1 bits as input so that the number of satisfying assignments of <i>φ</i> is equal to <i>c</i><sub>1</sub> + (2<sup><i>n</i></sup> − <i>c</i><sub>2</sub>), where <i>c</i><sub>1</sub> and <i>c</i><sub>2</sub> be the numbers of satisfying assignments of <i>φ</i><sub>1</sub> and <i>φ</i><sub>2</sub>, respectively.  Then the number of satisfying assignments of <i>φ</i> is equal to 2<sup><i>n</i></sup> if and only if <i>c</i><sub>1</sub>=<i>c</i><sub>2</sub>.</p>

CC BY-SA 2.5
2010-11-17T02:12:40.947Z
@Kaveh: Can you elaborate?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-17T03:27:29.227Z
The way to construct the boolean formula φ from the formulas φ_1 and φ_2 which I had in mind is as follows: add fresh variable x, and construct $\phi=(x\wedge\phi_1)\vee(\bar{x}\wedge\overline{\phi_2})$.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-17T11:03:17.130Z
@Kaveh: No, that is not what we want.  We want to decide whether φ_1 and φ_2 have the same _number_ of satisfying assignments, not necessarily the same set of satisfying assignments.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-17T19:36:51.157Z
@Tsuyoshi: Based on your definition of $C_=P$, is GI in $C_=P$? I think at least GI$\subseteq FP^{C_=P}$.
Mike Chen
CC BY-SA 2.5
2010-11-18T00:12:39.893Z
@Mike: Thank you for the interesting comment.  Are you talking about the result that Graph Isomorphism ∈ [SPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#spp) (Arvind and Kurur 2006 http://dx.doi.org/10.1016/j.ic.2006.02.002)?  If so, you are right; SPP is contained in $\mathrm{C}_=\mathrm{P}$, so Graph Isomorphism ∈ $\mathrm{C}_=\mathrm{P}$.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-18T00:23:06.197Z
@Mike: I learned that before the result GraphIso∈SPP, it was known that GraphIso ∈ [LWPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:L#lwpp): [Köbler, Schöning and Torán 1992](http://www.springerlink.com/content/g24030566wm73508/).  Since LWPP ⊆ [WPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:W#wpp) ⊆ $\mathrm{C}_=\mathrm{P}$, we did not need the stronger result by Arvind and Kurur to say that GraphIso∈$\mathrm{C}_=\mathrm{P}$.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-18T00:25:16.367Z
@Tsuyoshi: Thank you for your helpful answer.
Mike Chen
CC BY-SA 3.0
2014-05-17T09:18:53.107Z
Why is $\bar \phi_2$ a CNF?
domotorp
CC BY-SA 2.5
2010-11-17T01:11:33.427Z
2010-11-17T04:12:24.230Z
2010-11-17T04:12:24.230Z
Tsuyoshi Ito
<p>Given two CNF, if they have the same number of assignments to make them true, answer "Yes", otherwise answer "No".</p>

<p>It is easy to see it is in $P^{\#P}$, since if we know the exact numbers of solutions to these two CNF, we just campare them and answer "Yes" or "No".</p>

<p>What is the complexity of this problem?</p>

<cc.complexity-theory><complexity-classes><counting-complexity>
The complexity of checking whether two CNF have the same number of solutions
Mike Chen
# The complexity of checking whether two CNF have the same number of solutions

(Asked by: username_0 on 2010-11-16)

Given two CNF, if they have the same number of assignments to make them true, answer "Yes", otherwise answer "No".

It is easy to see it is in $P^{\#P}$, since if we know the exact numbers of solutions to these two CNF, we just campare them and answer "Yes" or "No".

What is the complexity of this problem?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity

---

## 3 answers

### Answer by username_4 on 2010-11-17. Score: 14 | Accepted answer

The problem is [coNP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#conp)-hard; you can easily reduce the UNSAT problem to this problem.

A more precise characterization is that the problem is [C=P](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#cequalsp)-complete. In fact, one definition of the class C=P is that it is the class of problems which are polynomial-time many-one reducible to this very problem (usually this definition is stated in terms of [GapP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aG#gapp) functions). But since this does not tell much, let me define this class in another way.

Let C=P be the class of problems which are polynomial-time many-one reducible to the following problem: given a boolean circuit *φ* and an integer *K* (in binary), decide whether the number of satisfying assignments of *φ* is equal to *K*. By a standard reduction which shows the #P-completeness of #3SAT, we can restrict *φ* to be a 3CNF formula without affecting the class. The class C=P contains a class called [US](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aU#us), which contains both [UP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aU#up) and coNP.

With this definition, your problem is C=P-complete. Actually, the C=P-hardness is easy to see from the definition of the class C=P (which uses 3CNF formulas).

To prove the membership in C=P, suppose that we are to decide whether two given CNF formulas *φ*1 and *φ*2 have the same number of satisfying assignments or not. Without loss of generality we can assume that the two formulas have the same number of variables, say *n*. Construct a boolean circuit *φ* which takes *n*+1 bits as input so that the number of satisfying assignments of *φ* is equal to *c*1 + (2*n* − *c*2), where *c*1 and *c*2 be the numbers of satisfying assignments of *φ*1 and *φ*2, respectively. Then the number of satisfying assignments of *φ* is equal to 2*n* if and only if *c*1=*c*2.

> **Comments:**
> **username_4**: @Kaveh: Can you elaborate?  
> **username_4**: The way to construct the boolean formula φ from the formulas φ_1 and φ_2 which I had in mind is as follows: add fresh variable x, and construct $\phi=(x\wedge\phi_1)\vee(\bar{x}\wedge\overline{\phi_2})$.  
> **username_4**: @Kaveh: No, that is not what we want.  We want to decide whether φ_1 and φ_2 have the same _number_ of satisfying assignments, not necessarily the same set of satisfying assignments.  
> **username_0**: @Tsuyoshi: Based on your definition of $C_=P$, is GI in $C_=P$? I think at least GI$\subseteq FP^{C_=P}$.  
> **username_4**: @Mike: Thank you for the interesting comment.  Are you talking about the result that Graph Isomorphism ∈ [SPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#spp) (Arvind and Kurur 2006 http://dx.doi.org/10.1016/j.ic.2006.02.002)?  If so, you are right; SPP is contained in $\mathrm{C}_=\mathrm{P}$, so Graph Isomorphism ∈ $\mathrm{C}_=\mathrm{P}$.  
> **username_4**: @Mike: I learned that before the result GraphIso∈SPP, it was known that GraphIso ∈ [LWPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:L#lwpp): [Köbler, Schöning and Torán 1992](http://www.springerlink.com/content/g24030566wm73508/).  Since LWPP ⊆ [WPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:W#wpp) ⊆ $\mathrm{C}_=\mathrm{P}$, we did not need the stronger result by Arvind and Kurur to say that GraphIso∈$\mathrm{C}_=\mathrm{P}$.  
> **username_0**: @Tsuyoshi: Thank you for your helpful answer.  
> **username_6**: Why is $\bar \phi_2$ a CNF?  

---

### Answer by username_1 on 2010-11-16. Score: 6

Here's a small variation on the original question. Let $O$ be an oracle which, on input $(f\_1,f\_2)$ outputs 1 if CNF $f\_1$ has **more** solutions than CNF $f\_2$.

Given this oracle, we build a poly-time machine $M$ which can solve the #P-complete problem of computing the number of solutions to a given CNF $\varphi$. Note that that $\varphi$ can have an exponential number of solutions.

$M$ works as follows: It generates formulas with known number of solutions, and using binary search and by asking at most polynomial queries to $O$, it finds a formulas $\varphi\_i$ which has **the same** number of solutions as $\varphi$. It finally outputs the number of solutions just found.

This shows that $M^O$ has complexity #P.

> **Comments:**
> **username_2**: Forgive my ignorance, but how do you generate a formula with a pre-specified number of solutions?  
> **username_3**: Let M be a (k+1)-bit number $M = \sum_{i=0}^k m_i 2^i$, and let $S$ be the indices $i$ where $m_i=1$. Make a formula with variables $x_0, \ldots, x_k$ and $y_0, \ldots, y_k$. For each $i \in S$, let $F_i$ be the following subformula: "All of $\{x_0,\ldots,x_{k-i}\}$ are true AND among $\{y_0, \ldots, y_k\}$ only $y_i$ is true." $F_i$ has $2^i$ satisfying assignments (the variables $\{x_{k-i+1}, \ldots, x_k\}$ are free), and for $i\ne j$, the satisfying assignments of $F_i$ and $F_j$ are disjoint due to the $y$ variables. The formula $\bigvee_{i\in S} F_i$ has $M$ satisfying assignments.  
> **username_4**: Note that it is PP-complete to decide whether, given two CNF formulas f_1 and f_2, f_1 has more satisfying assignments than f_2 or not.  
> **username_2**: @mikero: Ah, stupid me! I should have imagined that. Thanks for your illuminating explanation.  

---

### Answer by username_5 on 2010-11-16. Score: 5

It seems like it's atleast NP-hard as one can easily construct a SAT formula with just one solution. Then by the Valiant-Vazirani theorem, there's a probabilistic reduction from every SAT formula to a set of Unique-SAT problems (determining whether a formula has a unique solution) and comparing those Unique-SAT problems with the constructed SAT formula with just one solution enables you to determine the satisfiability of the SAT formula under consideration.

> **Comments:**
> **username_4**: To be precise, the first sentence should mention “under randomized reducibility” (although you mention it in the second sentence).  

---

