patternMinor
distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete
Viewed 0 times
textbfcompletebetweendistinctionand
Problem
We know that $\# \textbf{P}$ is closed under polynomial sums, i.e., sum of polynomially many $\# \textbf{P}$ functions is still in $\# \textbf{P}$.
Functions in $\textbf{P}^{\# \textbf{P}}$ are those which make polynomially many (non-parallel) queries to an oracle for a $\# \textbf{P}$-Complete problem. So, the computational complexity of such problems must be a sum of polynomially many $\# \textbf{P}$ functions. Due to the closure property, this sum will be in $\# \textbf{P}$.
If the above is right, then:
What is the difference between the classes $\# \textbf{P}$-Complete and $P^{\# \textbf{P}}$ ?
Thanks.
Functions in $\textbf{P}^{\# \textbf{P}}$ are those which make polynomially many (non-parallel) queries to an oracle for a $\# \textbf{P}$-Complete problem. So, the computational complexity of such problems must be a sum of polynomially many $\# \textbf{P}$ functions. Due to the closure property, this sum will be in $\# \textbf{P}$.
If the above is right, then:
What is the difference between the classes $\# \textbf{P}$-Complete and $P^{\# \textbf{P}}$ ?
Thanks.
Solution
First they are different kind of problems. One is a class of decision problems, the other one is a class of function problems. So lets interpret the question as $\mathsf{FP^{\#P}}$ vs. $\mathsf{\#P\text{-}complete}$.
Second, the kind of reductions used for completeness are not simple polynomial time Turing reductions, see the definition of #P-complete.
A polynomial time TM with access to a $\mathsf{\#P}$ problem might be able to do things that a $\mathsf{\#P}$ machine cannot do. For example, it can check if a $\Sigma^p_2$ formula is satisfiable and output $1$ if it is and $0$ if it is not.
Second, the kind of reductions used for completeness are not simple polynomial time Turing reductions, see the definition of #P-complete.
A polynomial time TM with access to a $\mathsf{\#P}$ problem might be able to do things that a $\mathsf{\#P}$ machine cannot do. For example, it can check if a $\Sigma^p_2$ formula is satisfiable and output $1$ if it is and $0$ if it is not.
Context
StackExchange Computer Science Q#2880, answer score: 3
Revisions (0)
No revisions yet.