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

<p><strong>input:</strong> <em>A Boolean formula <span class="math-container">$\phi\big(b=(b_1,b_2,\ldots,b_n), x=(x_1, x_2,\ldots, x_m)\big)$</span></em></p>

<p><strong>output:</strong> <em>The maximum, over all assignments to <span class="math-container">$b$</span>, of the number of assignments to <span class="math-container">$x$</span> such that <span class="math-container">$\phi(b, x)$</span> is satisfied (evaluates to true).</em></p>

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

<p><strong>Lemma 1.</strong> <em>The problem above is OPT#P-complete under polynomial-time reductions.</em></p>

<p><em>Proof sketch.</em> The proof is a simple variant of the standard proof that SAT is NP-complete.</p>

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

<p>So fix any such TM <span class="math-container">$M$</span> and corresponding <span class="math-container">$g$</span>.  Given any <span class="math-container">$w$</span>, the reduction will produce (in time poly<span class="math-container">$(|w|)$</span>) an equivalent instance of the problem in question: a Boolean formula <span class="math-container">$f_w(B, X)$</span> with Boolean variables <span class="math-container">$(B, X)$</span> such that</p>

<p><span class="math-container">$$g(w) = \max_{b} \#f_w(b),$$</span></p>

<p>where <span class="math-container">$\# f_w(b)$</span> is the number of assignments <span class="math-container">$X=x$</span> such that <span class="math-container">$f_w(b, x)$</span> is true.  </p>

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

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

CC BY-SA 4.0
2019-11-09T21:49:51.270Z
2019-11-09T21:56:20.173Z
2019-11-09T21:56:20.173Z
Neal Young
<p>Consider the following problem <span class="math-container">$\mathcal{P}$</span>.</p>

<p><strong>Instance</strong>: A Boolean formula <span class="math-container">$F$</span> of <span class="math-container">$n$</span> Boolean variables (<span class="math-container">$x_1,...,x_n$</span>) and <span class="math-container">$m$</span> Boolean parameters (<span class="math-container">$b_1,...,b_m$</span>) where <span class="math-container">$0 \leq m \leq n$</span>.</p>

<p><strong>Problem</strong>: Find an assignment <span class="math-container">$b_1^*,...,b_m^*$</span> to the parameters <span class="math-container">$b_1,...,b_m$</span> such that the number of satisfying assignments to the variables <span class="math-container">$x_1,...,x_n$</span> of <span class="math-container">$F(b_1/b_1^*,...,b_m/b_m^*)$</span> is minimum.</p>

<p>For example, <span class="math-container">$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\}$</span> where <span class="math-container">$n = 3$</span> and <span class="math-container">$m = 2$</span>.</p>

<p>If <span class="math-container">$(b_1^*,b_2^*) = (0,0)$</span>, then the number of satisfying assignments of <span class="math-container">$F(b_1/b_1^*,b_2/b_2^*)$</span> is 2.</p>

<p>If <span class="math-container">$(b_1^*,b_2^*) = (0,1)$</span>, then the number of satisfying assignments of <span class="math-container">$F(b_1/b_1^*,b_1/b_2^*)$</span> is 3.</p>

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

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

CC BY-SA 4.0
2019-11-03T07:35:44.503Z
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
CC BY-SA 4.0
2019-11-04T14:41:07.450Z
> "_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
CC BY-SA 4.0
2019-11-04T15:05:59.600Z
@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
CC BY-SA 4.0
2019-11-04T15:34:18.100Z
@NealYoung Thank for your comment. I have removed the content of case $m = 0$ from the question. > 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? No, the answer does not need to include the number of satisfying assignments to $x$ for the resulting formula.
Giang Trinh
CC BY-SA 4.0
2019-11-04T16:00:34.630Z
@NealYoung Yes. This problem is neither a decision problem or a counting problem. > To me the natural form would be to compute the min, over all b, of the number of satisfying x's. Yes, since this problem can be an optimization problem. What do you think about its hardness?
Giang Trinh
CC BY-SA 4.0
2019-11-04T16:34:02.570Z
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
CC BY-SA 4.0
2019-11-06T10:39:11.633Z
@Shaull > "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." Could you please show why this problem is #P? Clearly, it is a decision problem (not a counting problem).
Giang Trinh
CC BY-SA 4.0
2019-11-06T11:00:19.320Z
@NealYoung > "It doesn't have the correct syntactic form to belong to an existing complexity class." It seems to be an optimization problem whose measure function is a #P function, thus in Opt#P. However, I am not sure about this.
Giang Trinh
CC BY-SA 4.0
2019-11-06T11:13:31.523Z
@GiangTrinh - right, I meant the problem of computing the minimal number of satisfying assignments for any assignments to the b's.
Shaull
CC BY-SA 4.0
2019-11-06T16:08:18.843Z
What is Opt#P? Is that a standard class? I don't see it here https://complexityzoo.uwaterloo.ca/Complexity_Zoo:O, and OptP doesn't seem to be what you have in mind.   Also, your comment suggests that you have in mind that the output for the problem is the minimum number of satisfying assignments.. but as you've defined the problem in the post the output is _an assignment_.
Neal Young
CC BY-SA 4.0
2019-11-06T18:11:42.580Z
@NealYoung > "What is Opt#P? Is that a standard class? I don't see it here complexityzoo.uwaterloo.ca/Complexity_Zoo:O, and OptP doesn't seem to be what you have in mind." Opt#P is a class defined for quantum optimization problems (see https://arxiv.org/abs/quant-ph/0204010). Let $\mathcal{P}$ be the problem in my post. The output of its constructive version is an assignment to $b_1, ..., b_m$ and the minimum number of satisfying assignments to $x_1, ..., x_n$. Here, I consider the constructive version.
Giang Trinh
CC BY-SA 4.0
2019-11-06T19:14:04.250Z
I find your question confusing.  You first say the problem is $\mathcal{P}$, then effectively later in your post you say "oh wait, never mind, I am actually interested in $\mathcal{P}_C$".  Why not [edit] your question to introduce $\mathcal{P}_C$ from the start and skip $\mathcal{P}$?
D.W.
CC BY-SA 4.0
2019-11-06T22:12:45.920Z
As currently defined the problem $\cal P_C$ can't be in #P, because the output is defined to include an assignment.  Each element of #P must be a function whose output is a non-negative number.  (See https://en.wikipedia.org/wiki/♯P).  For this reason, $\cal P_C$ as currently defined can't be #P complete.  There seems to be some basic confusion about what it means formally for a problem to be in a given class.
Neal Young
CC BY-SA 4.0
2019-11-06T22:28:08.067Z
Per https://arxiv.org/abs/quant-ph/0204010, Opt#P contains functions of the form $f(\phi) = \max_b g(\phi, b)$ where $b$ ranges over strings of length polynomial in $|\phi|$, and $g$ is in #P.  That is, for some non-deterministic TM $M$ that on input $(\phi, b)$ runs in time poly in $|\phi|$, $g(\phi, b)$ is the number of accepting computations of $M$ on $(\phi, b)$.  If $M(\phi, b)$ interprets $\phi$ as a Boolean formula and $b$ as a partial assignment, guesses an assignment $x$ to the rest, and rejects if $\phi$ is satisfied, we have (a variant of) OP's problem.  Surely it's Opt#P-complete.
Neal Young
CC BY-SA 4.0
2019-11-07T05:41:12.417Z
@D.W. I am sorry for this confusion. At the start, I unclearly understood my problem.
Giang Trinh
CC BY-SA 4.0
2019-11-07T06:16:12.463Z
That's fine, but now that you understand more clearly, you can edit your question to improve it.  Rather than apologizing in the comments, even better would be to [edit] the question based on your current understanding and the feedback you've received.  Presumably you don't need to mention the version of the problem that aims to find the assignment at all, and just say that the problem is to find the minimum number of assignments.
D.W.
CC BY-SA 4.0
2019-11-09T09:29:07.233Z
@NealYoung > "Opt#P contains functions of ... we have (a variant of) OP's problem. " Thank you for your detailed explanations. I think this only shows that $\mathcal{P}_C$ is in Opt#P. In order to prove $\mathcal{P}_C$ is Opt#P-complete, we need a proof like the proof for the completeness of SAT (see https://en.m.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem) or a reduction of $\mathcal{P}_C$ to a known Opt#P-complete problem.
Giang Trinh
CC BY-SA 4.0
2019-11-09T21:50:46.253Z
Sure, I think that holds.  I'll add a proof sketch as an answer.
Neal Young
<cc.complexity-theory><complexity-classes>
Which complexity class does this problem belong to?
Giang Trinh
# Which complexity class does this problem belong to?

(Asked by: username_0 on 2019-11-02)

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.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: 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  
> **username_2**: > "_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?  
> **username_0**: @username_1 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$?  
> **username_0**: @NealYoung Thank for your comment. I have removed the content of case $m = 0$ from the question. > 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? No, the answer does not need to include the number of satisfying assignments to $x$ for the resulting formula.  
> **username_0**: @NealYoung Yes. This problem is neither a decision problem or a counting problem. > To me the natural form would be to compute the min, over all b, of the number of satisfying x's. Yes, since this problem can be an optimization problem. What do you think about its hardness?  
> **username_2**: 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.  
> **username_0**: @username_1 > "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." Could you please show why this problem is #P? Clearly, it is a decision problem (not a counting problem).  
> **username_0**: @NealYoung > "It doesn't have the correct syntactic form to belong to an existing complexity class." It seems to be an optimization problem whose measure function is a #P function, thus in Opt#P. However, I am not sure about this.  
> **username_1**: @GiangTrinh - right, I meant the problem of computing the minimal number of satisfying assignments for any assignments to the b's.  
> **username_2**: What is Opt#P? Is that a standard class? I don't see it here https://complexityzoo.uwaterloo.ca/Complexity_Zoo:O, and OptP doesn't seem to be what you have in mind.   Also, your comment suggests that you have in mind that the output for the problem is the minimum number of satisfying assignments.. but as you've defined the problem in the post the output is _an assignment_.  
> **username_0**: @NealYoung > "What is Opt#P? Is that a standard class? I don't see it here complexityzoo.uwaterloo.ca/Complexity_Zoo:O, and OptP doesn't seem to be what you have in mind." Opt#P is a class defined for quantum optimization problems (see https://arxiv.org/abs/quant-ph/0204010). Let $\mathcal{P}$ be the problem in my post. The output of its constructive version is an assignment to $b_1, ..., b_m$ and the minimum number of satisfying assignments to $x_1, ..., x_n$. Here, I consider the constructive version.  
> **username_3**: I find your question confusing.  You first say the problem is $\mathcal{P}$, then effectively later in your post you say "oh wait, never mind, I am actually interested in $\mathcal{P}_C$".  Why not [edit] your question to introduce $\mathcal{P}_C$ from the start and skip $\mathcal{P}$?  
> **username_2**: As currently defined the problem $\cal P_C$ can't be in #P, because the output is defined to include an assignment.  Each element of #P must be a function whose output is a non-negative number.  (See https://en.wikipedia.org/wiki/♯P).  For this reason, $\cal P_C$ as currently defined can't be #P complete.  There seems to be some basic confusion about what it means formally for a problem to be in a given class.  
> **username_2**: Per https://arxiv.org/abs/quant-ph/0204010, Opt#P contains functions of the form $f(\phi) = \max_b g(\phi, b)$ where $b$ ranges over strings of length polynomial in $|\phi|$, and $g$ is in #P.  That is, for some non-deterministic TM $M$ that on input $(\phi, b)$ runs in time poly in $|\phi|$, $g(\phi, b)$ is the number of accepting computations of $M$ on $(\phi, b)$.  If $M(\phi, b)$ interprets $\phi$ as a Boolean formula and $b$ as a partial assignment, guesses an assignment $x$ to the rest, and rejects if $\phi$ is satisfied, we have (a variant of) OP's problem.  Surely it's Opt#P-complete.  
> **username_0**: @username_3 I am sorry for this confusion. At the start, I unclearly understood my problem.  
> **username_3**: That's fine, but now that you understand more clearly, you can edit your question to improve it.  Rather than apologizing in the comments, even better would be to [edit] the question based on your current understanding and the feedback you've received.  Presumably you don't need to mention the version of the problem that aims to find the assignment at all, and just say that the problem is to find the minimum number of assignments.  
> **username_0**: @NealYoung > "Opt#P contains functions of ... we have (a variant of) OP's problem. " Thank you for your detailed explanations. I think this only shows that $\mathcal{P}_C$ is in Opt#P. In order to prove $\mathcal{P}_C$ is Opt#P-complete, we need a proof like the proof for the completeness of SAT (see https://en.m.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem) or a reduction of $\mathcal{P}_C$ to a known Opt#P-complete problem.  
> **username_2**: Sure, I think that holds.  I'll add a proof sketch as an answer.  

---

## 1 answers

### Answer by username_2 on 2019-11-09. Score: 2 | Accepted answer

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$


---

