# Which complexity class does this problem belong to?

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.

• 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 – Shaull Nov 3 '19 at 7:35
• > "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? – Neal Young Nov 4 '19 at 14:41
• @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$? – Giang Trinh Nov 4 '19 at 15:05
• 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. – Neal Young Nov 4 '19 at 16:34
• Sure, I think that holds. I'll add a proof sketch as an answer. – 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$$