10
$\begingroup$

I was trying to understand these classes but always got confused ... the questions are :

What is the relation between $FNP$ and $\#P$ , in particular is it an open question ?

What is the relation of $\oplus P$ and $NP$ ? is this question open ?

What about the relationship between $PH$ and $P^{FNP}$ ? is this question open ?

$\endgroup$
4
  • 1
    $\begingroup$ $FNP \subseteq P^{\#P}$, $NP \subseteq RP^{\oplus P}$ and $P^{FNP}$ is contained in Functional Polynomial Hierarchy, which is called $FPH$. $\endgroup$
    – Tayfun Pay
    Aug 29, 2013 at 0:16
  • $\begingroup$ @Tayfun , there is something not making sense : $FNP\subseteq P^{\#P}$ the first is class of function while the later is class of decision problems . $\endgroup$ Aug 29, 2013 at 1:02
  • $\begingroup$ @Tayfun could you please list the references proving these results. $\endgroup$ Aug 29, 2013 at 1:21
  • $\begingroup$ I think that $FNP$ is properly contained in $\#P$. If i'm not mistaken Toda's theorem implies that if $FNP=\#P$ the polynomial hierarchy collapses to $\Delta^P_2$. $\endgroup$
    – plm
    May 12 at 13:00

1 Answer 1

4
+50
$\begingroup$

1)$\bf FNP$ is contained in $\bf FPH$, which is called the "functional polynomial hierarchy", where every function in $\bf FPH$ is polynomial time 1-Turing reduciable to some function in $\bf \#P$.
2)We know from the Valiant Vazirani theorem that $\bf NP$ $\subseteq$ $\bf RP^{PromiseUP}$. We also know that $\bf UP$ $\subseteq$ $\bf \oplus P$. Therefore, we have $\bf NP$ $\subseteq$ $\bf RP^{\bf \oplus P}$.

$\endgroup$
4
  • $\begingroup$ hi , thank you a lot , could you list references ? $\endgroup$ Aug 31, 2013 at 2:50
  • $\begingroup$ 2) L.G. Valiant & V. Vazirani “NP is as easy as detecting Unique Solutions” Theoretical Computer Science 47 (1986) pp. 85-93. $\endgroup$
    – Tayfun Pay
    Aug 31, 2013 at 3:09
  • $\begingroup$ 1)S. Toda, O. Watanabe. “Polynomial-time 1-Turing reductions from #PH to #P.” Theoretical Computer Science. Volume 100. Pages 205-221. 1992. $\endgroup$
    – Tayfun Pay
    Aug 31, 2013 at 3:09
  • $\begingroup$ cstheory.stackexchange.com/questions/6404/… $\endgroup$
    – Tayfun Pay
    Aug 31, 2013 at 3:10

Your Answer

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

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