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$
  • 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 '13 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$ – Fayez Abdlrazaq Deab Aug 29 '13 at 1:02
  • $\begingroup$ @Tayfun could you please list the references proving these results. $\endgroup$ – Fayez Abdlrazaq Deab Aug 29 '13 at 1:21
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$
  • $\begingroup$ hi , thank you a lot , could you list references ? $\endgroup$ – Fayez Abdlrazaq Deab Aug 31 '13 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 '13 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 '13 at 3:09
  • $\begingroup$ cstheory.stackexchange.com/questions/6404/… $\endgroup$ – Tayfun Pay Aug 31 '13 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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