<p>It's in $\mathrm{FP^{\#P}}$, since you can compute it in poly time using oracle calls to compute the&nbsp;$f$s.  If you can poly-time Turing reduce a $\mathrm{\#P}$-complete problem to it, then $\tilde{f}$&nbsp;is $\mathrm{\#P}$-hard but you can't say it's $\mathrm{\#P}$-complete unless you can show that it's in&nbsp;$\mathrm{\#P}$. That seems unlikely, to me, as I can't see any way of building a nondeterministic Turing machine to have that many accepting paths.</p>

<p>Since $\tilde{f}\in\mathrm{FP^{\#P}}$ and $\mathrm{FP^{FP^{\#P}}}=\mathrm{FP^{\#P}}$ (just compose the reductions), $\mathrm{FP}^{\tilde{f}}\subseteq \mathrm{FP^{\#P}}$.  Note that $\mathrm{FP}^{\tilde{f}}$ is a complexity class (all problems that are poly-time Turing reducible to&nbsp;$\tilde{f}$), not a problem.</p>

CC BY-SA 3.0
2013-09-03T18:11:44.770Z
Since I mentioned that $F$ is the set of all $\#P$ functions and $\tilde{f}$ is one of them, can't we say that $\tilde{f} \in\#P-\text{Complete}$ ?
Pavithran Iyer
CC BY-SA 3.0
2013-09-03T20:09:34.700Z
$\tilde{f}$ is the maximum of a set of \#P functions, and that isn't obviously in \#P. Why do you think it's in \#P?
David Richerby
CC BY-SA 3.0
2013-09-05T17:31:47.570Z
Sorry if I am missing something. "$\tilde{f}$ is the maximum amongst the set of all $\# P$ functions", which means $\tilde{f}$ is in $\# P$ because the maximization is only over the set of $\# P$ functions. Right ?
Pavithran Iyer
CC BY-SA 3.0
2013-09-05T21:12:14.887Z
The definition given was $\tilde{f}(x) = \max_{f\in F}f(x)$, for some set $F\subseteq \#P$. That doesn't imply that $\tilde{f}\in F$, since the max is performed separately for each value of $x$.
David Richerby
CC BY-SA 3.0
2013-08-18T08:08:28.187Z
2013-08-18T08:08:28.187Z
David Richerby
<p>It seems to be an optimization problem whose measure function is a #P function, thus it is in Opt#P (see <a href="https://arxiv.org/abs/quant-ph/0204010" rel="nofollow noreferrer">https://arxiv.org/abs/quant-ph/0204010</a>).</p>

<p>I realized that your problem is related to a problem which I am considering to. You can see <a href="https://cstheory.stackexchange.com/questions/45784/which-complexity-class-does-this-problem-belong-to?noredirect=1#comment101859_45784">Which complexity class does this problem belong to?</a></p>

CC BY-SA 4.0
2019-11-08T19:49:45.497Z
2019-11-08T19:49:45.497Z
Giang Trinh
<p>Is there any complexity class which contains problems that can be expressed as an optimization over polynomially many #P functions ? i.e:</p>

<p>$$\tilde{f}(x) = \text{Max}_{f \in F}f(x)$$</p>

<p>where $f\in\# P$.</p>

<p>Moreover, if I can reduce a #P-Complete function to this, by means of a polynomial time Turing reduction, am I allowed to say formally that: </p>

<p>$$\tilde{f} \in \#P-\text{Complete}$$</p>

<p>OR</p>

<p>$$FP^{\tilde{f}} \in FP^{\#P} $$</p>

<p>The latter seems more plausible to me than the former, but could anyone please tell me if I could use the former claim.</p>

<complexity-classes><optimization><counting-complexity>
Complexity class for Optimization problems over #P functions
Pavithran Iyer
# Complexity class for Optimization problems over #P functions

(Asked by: username_0 on 2013-08-18)

Is there any complexity class which contains problems that can be expressed as an optimization over polynomially many #P functions ? i.e:

$$\tilde{f}(x) = \text{Max}\_{f \in F}f(x)$$

where $f\in\# P$.

Moreover, if I can reduce a #P-Complete function to this, by means of a polynomial time Turing reduction, am I allowed to say formally that:

$$\tilde{f} \in \#P-\text{Complete}$$

OR

$$FP^{\tilde{f}} \in FP^{\#P} $$

The latter seems more plausible to me than the former, but could anyone please tell me if I could use the former claim.

**Tags:** complexity-classes, optimization, counting-complexity

---

## 2 answers

### Answer by username_1 on 2013-08-18. Score: 4 | Accepted answer

It's in $\mathrm{FP^{\#P}}$, since you can compute it in poly time using oracle calls to compute the $f$s. If you can poly-time Turing reduce a $\mathrm{\#P}$-complete problem to it, then $\tilde{f}$ is $\mathrm{\#P}$-hard but you can't say it's $\mathrm{\#P}$-complete unless you can show that it's in $\mathrm{\#P}$. That seems unlikely, to me, as I can't see any way of building a nondeterministic Turing machine to have that many accepting paths.

Since $\tilde{f}\in\mathrm{FP^{\#P}}$ and $\mathrm{FP^{FP^{\#P}}}=\mathrm{FP^{\#P}}$ (just compose the reductions), $\mathrm{FP}^{\tilde{f}}\subseteq \mathrm{FP^{\#P}}$. Note that $\mathrm{FP}^{\tilde{f}}$ is a complexity class (all problems that are poly-time Turing reducible to $\tilde{f}$), not a problem.

> **Comments:**
> **username_0**: Since I mentioned that $F$ is the set of all $\#P$ functions and $\tilde{f}$ is one of them, can't we say that $\tilde{f} \in\#P-\text{Complete}$ ?  
> **username_1**: $\tilde{f}$ is the maximum of a set of \#P functions, and that isn't obviously in \#P. Why do you think it's in \#P?  
> **username_0**: Sorry if I am missing something. "$\tilde{f}$ is the maximum amongst the set of all $\# P$ functions", which means $\tilde{f}$ is in $\# P$ because the maximization is only over the set of $\# P$ functions. Right ?  
> **username_1**: The definition given was $\tilde{f}(x) = \max_{f\in F}f(x)$, for some set $F\subseteq \#P$. That doesn't imply that $\tilde{f}\in F$, since the max is performed separately for each value of $x$.  

---

### Answer by username_2 on 2019-11-08. Score: 0

It seems to be an optimization problem whose measure function is a #P function, thus it is in Opt#P (see <https://arxiv.org/abs/quant-ph/0204010>).

I realized that your problem is related to a problem which I am considering to. You can see [Which complexity class does this problem belong to?](https://cstheory.stackexchange.com/questions/45784/which-complexity-class-does-this-problem-belong-to?noredirect=1#comment101859_45784)


---

