Consider the following problem $\mathcal{P}$.

Instance: A Boolean formula $F$ of $n$ Boolean variables ($x_1,...,x_n$) and $m$ Boolean parameters ($b_1,...,b_m$) where $0 \leq m \leq n$.

Problem: Find an assignment $b_1^*,...,b_m^*$ to the parameters $b_1,...,b_m$ such that the number of satisfying assignments to the variables $x_1,...,x_n$ of $F(b_1/b_1^*,...,b_m/b_m^*)$ is minimum.

For example, $F = \{((x_2 \lor x_3) \leftrightarrow x_1) \lor (x_1 \leftrightarrow b_1 \land (x_2 \lor x_3) \leftrightarrow \neg b_1)\} \land \{((x_1 \land \neg x_2) \leftrightarrow x_2) \lor (x_2 \leftrightarrow b_2 \land (x_1 \land \neg x_2) \leftrightarrow \neg b_2)\} \land \{x_1 \leftrightarrow x_3\}$ where $n = 3$ and $m = 2$.

If $(b_1^*,b_2^*) = (0,0)$, then the number of satisfying assignments of $F(b_1/b_1^*,b_2/b_2^*)$ is 2.

If $(b_1^*,b_2^*) = (0,1)$, then the number of satisfying assignments of $F(b_1/b_1^*,b_1/b_2^*)$ is 3.

Here, I consider the constructive version $\mathcal{P}_C$ of $\mathcal{P}$ (i.e., the output of $\mathcal{P}_C$ includes the optimal assignment to $b_1, ..., b_m$ and the minimum number of assignments to $x_1, ..., x_n$). When $m = 0$, $\mathcal{P}_C$ is equivalent to #SAT, which is known as #P-complete. Thus, $\mathcal{P}_C$ is #P-hard. However, it is insufficient to conclude that $\mathcal{P}_C$ is #P-complete.

Which complexity class does this problem belong to (#P or other one)? If it does not belong to #P, please give me a proof.

  • 2
    $\begingroup$ What is the counting version and the decision version you are considering? As is, this is neither a decision problem nor a counting problem. If you ask e.g., does there exist an assignment for b such that the number of satisfying assignments for the variables is exactly k, then this is still in #P $\endgroup$
    – Shaull
    Nov 3 '19 at 7:35
  • 2
    $\begingroup$ > "When $m=0$, this problem is equivalent to #SAT, which is #P-hard. Thus, this problem is #P-hard. However, it is insufficient to conclude that this problem is in #P." No, when $m=0$, the problem as defined is trivial. There are no $b_i$s to assign to, so there is only one assignment to $b$ --- the empty assignment --- so finding the assignment for $b$ that minimizes anything is trivial, it has to be the empty assignment. Do you have in mind that the answer should include not just the assignment to $b$, but also the number of satisfying assignments to $x$ for the resulting formula? $\endgroup$
    – Neal Young
    Nov 4 '19 at 14:41
  • $\begingroup$ @Shaull Thank for your response. I think it is an optimization problem. Its decision version can be stated as: Is there an assignment to $b_1, ..., b_m$ such that the number of satisfying assignments of $F(b_1/b_1^*, ..., b_m/b_m^*)$ to $x_1, ..., x_n$ is at most $k$? $\endgroup$ Nov 4 '19 at 15:05
  • 1
    $\begingroup$ Okay, but as you've formulated the problem, for the reasons mentioned above, the answer to your question "Which complexity class does this problem belong to (#P or other one)?" is simply "none." It doesn't have the correct syntactic form to belong to an existing complexity class. To get a more meaningful answer to your question, I think you need to present the problem you have in mind in one of the standard forms. For most problems, that's not hard to do. $\endgroup$
    – Neal Young
    Nov 4 '19 at 16:34
  • 1
    $\begingroup$ Sure, I think that holds. I'll add a proof sketch as an answer. $\endgroup$
    – Neal Young
    Nov 9 '19 at 21:50

We'll argue that the following formulation of OP's problem is complete for OPT#P under poly-time reductions:

input: A Boolean formula $\phi\big(b=(b_1,b_2,\ldots,b_n), x=(x_1, x_2,\ldots, x_m)\big)$

output: The maximum, over all assignments to $b$, of the number of assignments to $x$ such that $\phi(b, x)$ is satisfied (evaluates to true).

The problem differs from OP's problem in two minor ways. First, the output does not include an assignment to $b$. Second, it chooses $b$ to maximize, rather than minimize, the number of satisfying assignments. However, OP's problem for a given $\phi$ is essentially equivalent to this problem for the complement of $\phi$.

Lemma 1. The problem above is OPT#P-complete under polynomial-time reductions.

Proof sketch. The proof is a simple variant of the standard proof that SAT is NP-complete.

First, as I understand it, OPT#P is the class of functions of the form $$g(w) = \max_b \#M(w, b)$$ for some non-deterministic poly-time TM $M$, where $\#M(w, b)$ is the number of accepting computation paths for $M$ on input $(w, b)$. In the $\max$, $b$ ranges over all binary strings of length equal to some fixed polynomial $p(|w|)$.

So fix any such TM $M$ and corresponding $g$. Given any $w$, the reduction will produce (in time poly$(|w|)$) an equivalent instance of the problem in question: a Boolean formula $f_w(B, X)$ with Boolean variables $(B, X)$ such that

$$g(w) = \max_{b} \#f_w(b),$$

where $\# f_w(b)$ is the number of assignments $X=x$ such that $f_w(b, x)$ is true.

Recall that the classical Cook-Levin reduction for $M$ on a given input $(w, b)$ first produces a formula $F(W,B,X)$ with boolean inputs $W$, $B$, and $X$, where $|W|=|w|$, $|B|=|b|$, and $|X|$ is some fixed polynomial in $|w|+|y|$. But then it adds constraints to force $W=w$ and $B=b$ (or makes these substitutions and simplifies the resulting formula), resulting in a formula $F_{wb}(X)$ such that there is exactly one assignment to $X$ that satisfies $f_{wb}(X)$ for each accepting computation of $M$ on input $(w, b)$. (The variables in $X$ encode the non-deterministic guesses of $M(w, b)$, and also auxiliary values that encode the rest of the computation. But the auxiliary values are determined by the non-deterministic guesses and $w$ and $b$.) In this way, $f_{wb}(X)$ is satisfiable if and only if $M(w, b)$ has an accepting computation.

Instead, given $w$, the reduction outputs the formula $f_w(B,X)$ obtained from $F(W,B,X)$ by adding only the constraints that force $W=w$. Then, for any given second argument $b$, the number of accepting computations of $M(w, b)$ is the number of assignments $X=x$ such that $f_w(b, x)$ is true. That is, in our previous notation, for all $b$, $$\#M(w, b) = \# f_w(b).$$ It follows that $g(w) = \max_b \# f_w(b)$ as desired.$~~~~~\Box$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.