Skip to main content
added 226 characters in body; edited title
Source Link
user1093
user1093

Is #P closed under exponentiation? modulo?

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?

Is #P closed under exponentiation?

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?

Is #P closed under exponentiation? modulo?

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?

added 61 characters in body
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Definition:${\bf \#P}$ = {$f$ | ($\exists$ a nondeterministic polynomial-time Turing machine $M$) ($\forall x$) [$f$($x$) =The complexity class $ \#accept_{M}$($x$)]}$\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 ${\bf \#P}$$\sharpp$ 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}$$\sharpp$ function $f$ and another ${\bf \#P}$$\sharpp$ function $g$. Is it true that $f^{g}$ or $g^{f}$ are ${\bf \#P}$$\sharpp$ functions as well?

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?

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?

Tweeted twitter.com/#!/StackCompSci/status/234754690699653120
added 12 characters in body
Source Link
user1093
user1093

Definition:${\bf \#P}$ = $\{f | (\exists${$f$ | ($\exists$ a nondeterministic polynomial-time Turing machine $M) (\forall x) [f (x) = \#accept_{M}(x)]\}$$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?

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?

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?

added 142 characters in body; edited title
Source Link
user1093
user1093
Loading
edited title
Link
user1093
user1093
Loading
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Loading
Source Link
user1093
user1093
Loading