14

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?

Mike Chen
  • 709
  • 4
  • 10

3 Answers3

14

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 + (2n − c2), 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.

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
  • @Kaveh: Can you elaborate? – Tsuyoshi Ito Nov 17 '10 at 02:12
  • 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 Nov 17 '10 at 03:27
  • 1
    @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 Nov 17 '10 at 11:03
  • 1
    @Tsuyoshi: Based on your definition of $C_=P$, is GI in $C_=P$? I think at least GI$\subseteq FP^{C_=P}$. – Mike Chen Nov 17 '10 at 19:36
  • 1
    @Mike: Thank you for the interesting comment. Are you talking about the result that Graph Isomorphism ∈ 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 Nov 18 '10 at 00:12
  • 1
    @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}$. – Tsuyoshi Ito Nov 18 '10 at 00:23
  • @Tsuyoshi: Thank you for your helpful answer. – Mike Chen Nov 18 '10 at 00:25
  • Why is $\bar \phi_2$ a CNF? – domotorp May 17 '14 at 09:18
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.

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
  • Forgive my ignorance, but how do you generate a formula with a pre-specified number of solutions? – Giorgio Camerani Nov 16 '10 at 20:13
  • 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. – mikero Nov 16 '10 at 21:36
  • 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 Nov 17 '10 at 02:56
  • @mikero: Ah, stupid me! I should have imagined that. Thanks for your illuminating explanation. – Giorgio Camerani Nov 17 '10 at 10:38
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.

Opt
  • 1,311
  • 14
  • 20
  • To be precise, the first sentence should mention “under randomized reducibility” (although you mention it in the second sentence). – Tsuyoshi Ito Nov 17 '10 at 03:41