3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Sorry, I must have said $\mathbf{FP}^{\# \mathsf{P}}$, as you pointed out. $\endgroup$ Jul 23 '12 at 21:10
  • $\begingroup$ Though the reductions can be many-to-one, shouldn't they still be poly-time reductions ? I have a reference here: link. Please correct me if am wrong. Also, why does the type of reduction affect the question ? Lastly, a $\Sigma^{p}_{2}$ formula can be written as (at most) poly(n) $\textbf{NP}$ formulae separated by $\wedge$. Isn't now a $\# \textbf{P}$ enough to decide the $\Sigma^{p}_{2}$ expression ? $\endgroup$ Jul 23 '12 at 21:33
  • $\begingroup$ No, $\Sigma^p_2 = \mathsf{NP^{NP}}$ is of the form $\{x \mid \exists y \leq 2^{n^{O(1)}}\forall z\leq 2^{n^{O(1)}} R(x,y,z) \}$ ($R \in mathsf{P}$) and it is not known that such a formula can be written as a (uniform) polynomial size disjunction of $\mathsf{coNP}$ sets (i.e. $\mathsf{P^{NP}}$). I gave you an example why the kind of reduction used matters. For intuition in a much simpler situation think about the difference between polytime many-one reduction and polytime Turing reductions to $SAT$. The former will be in $\mathsf{NP}$, the later also contains $\mathsf{coNP}$. $\endgroup$
    – Kaveh
    Jul 24 '12 at 4:35
  • $\begingroup$ I suggest reading a good complexity theory textbook like Arora and Barak, "Computational Complexity, A Modern Approach", 2009. $\endgroup$
    – Kaveh
    Jul 24 '12 at 4:36

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .