7
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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
    Commented Aug 13, 2012 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.