The complexity class $\newcommand{\sharpp}{\mathsf{\#P}}\sharpp$ is defined as

$\qquad \displaystyle \sharpp = \{f \mid \exists \text{ polynomial-time NTM } M\ \forall x.\, f(x) = \#\operatorname{accept}_{M}(x)\}$.

It is known that $\sharpp$ is closed under addition, multiplication and binomial coefficient. I was wondering if it is closed under power. For example, we are given a $\sharpp$ function $f$ and another $\sharpp$ function $g$. Is it true that $f^{g}$ or $g^{f}$ are $\sharpp$ functions as well?

This is edit after the question has been answered.

Is ($f$ modulo $g$) a $\sharpp$ function? How about when we are given a $\newcommand{\FP}{\mathsf{FP}}\FP$ function $h$. Then is ($f$ modulo $h$) a $\sharpp$ function?


No. Take $f(n)=g(n)=2^n$ for a counterexample.

  • 2
    $\begingroup$ @Geekster: It is bad form to extend a question after answers have been added (and even accepted). Please consider adding a new question for your new problem. $\endgroup$
    – Raphael
    Aug 13 '12 at 9:21

Your Answer

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