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 ?

Improve this question
$\endgroup$
3
  • 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$
    – Fayez Abdlrazaq Deab
    Aug 29, 2013 at 1:02
  • $\begingroup$ @Tayfun could you please list the references proving these results. $\endgroup$
    – Fayez Abdlrazaq Deab
    Aug 29, 2013 at 1:21

1 Answer 1

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ hi , thank you a lot , could you list references ? $\endgroup$
    – Fayez Abdlrazaq Deab
    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 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.