HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#2880, answer score: 3

Revisions (0)

No revisions yet.