3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$ ? $\endgroup$ – Pavithran Iyer Sep 3 '13 at 18:11
  • 1
    $\begingroup$ $\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? $\endgroup$ – David Richerby Sep 3 '13 at 20:09
  • $\begingroup$ 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 ? $\endgroup$ – Pavithran Iyer Sep 5 '13 at 17:31
  • 1
    $\begingroup$ 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$. $\endgroup$ – David Richerby Sep 5 '13 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.