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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry, I must have said $\mathbf{FP}^{\# \mathsf{P}}$, as you pointed out. $\endgroup$
    – Pavithran Iyer
    Jul 23, 2012 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$
    – Pavithran Iyer
    Jul 23, 2012 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, 2012 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, 2012 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.