[Solved]: Is #P closed under exponentiation? modulo?

Problem Detail: 

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?

Asked By : Tayfun Pay

Answered By : Tsuyoshi Ito

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3134

3.2K people like this

 Download Related Notes/Documents