# Complexity class for Optimization problems over #P functions

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.

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.
• 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 Sep 3 '13 at 18:11
• $\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 Sep 3 '13 at 20:09
• 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 Sep 5 '13 at 17:31
• 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 Sep 5 '13 at 21:12