Skip to main content
5 of 7
added 12 characters in body
user avatar
user avatar

Is #P closed under exponentiation?

Definition:${\bf \#P}$ = {$f$ | ($\exists$ a nondeterministic polynomial-time Turing machine $M$) ($\forall x$) [$f$($x$) = $ \#accept_{M}$($x$)]}.

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

user1093