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?


3 Answers 3


The problem is coNP-hard; you can easily reduce the UNSAT problem to this problem.

A more precise characterization is that the problem is C=P-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 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, which contains both 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 c1 + (2nc2), where c1 and c2 be the numbers of satisfying assignments of φ1 and φ2, respectively. Then the number of satisfying assignments of φ is equal to 2n if and only if c1=c2.

  • $\begingroup$ @Kaveh: Can you elaborate? $\endgroup$ Nov 17, 2010 at 2:12
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 17, 2010 at 11:03
  • 1
    $\begingroup$ @Tsuyoshi: Based on your definition of $C_=P$, is GI in $C_=P$? I think at least GI$\subseteq FP^{C_=P}$. $\endgroup$
    – Mike Chen
    Nov 17, 2010 at 19:36
  • 1
    $\begingroup$ @Mike: Thank you for the interesting comment. Are you talking about the result that Graph Isomorphism ∈ SPP (Arvind and Kurur 2006 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}$. $\endgroup$ Nov 18, 2010 at 0:12
  • 1
    $\begingroup$ @Mike: I learned that before the result GraphIso∈SPP, it was known that GraphIso ∈ LWPP: Köbler, Schöning and Torán 1992. Since LWPP ⊆ WPP ⊆ $\mathrm{C}_=\mathrm{P}$, we did not need the stronger result by Arvind and Kurur to say that GraphIso∈$\mathrm{C}_=\mathrm{P}$. $\endgroup$ Nov 18, 2010 at 0:23

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.

  • $\begingroup$ Forgive my ignorance, but how do you generate a formula with a pre-specified number of solutions? $\endgroup$ Nov 16, 2010 at 20:13
  • 3
    $\begingroup$ 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. $\endgroup$
    – mikero
    Nov 16, 2010 at 21:36
  • $\begingroup$ 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. $\endgroup$ Nov 17, 2010 at 2:56
  • $\begingroup$ @mikero: Ah, stupid me! I should have imagined that. Thanks for your illuminating explanation. $\endgroup$ Nov 17, 2010 at 10:38

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.

  • $\begingroup$ To be precise, the first sentence should mention “under randomized reducibility” (although you mention it in the second sentence). $\endgroup$ Nov 17, 2010 at 3:41

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.