Which complexity class does this problem belong to?

Question

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.

Answer 1

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$