# $FNP$ ,$\#P$,$\oplus P$ classes

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 ?

• $FNP \subseteq P^{\#P}$, $NP \subseteq RP^{\oplus P}$ and $P^{FNP}$ is contained in Functional Polynomial Hierarchy, which is called $FPH$. – Tayfun Pay Aug 29 '13 at 0:16
• @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 . – Fayez Abdlrazaq Deab Aug 29 '13 at 1:02
• @Tayfun could you please list the references proving these results. – Fayez Abdlrazaq Deab Aug 29 '13 at 1:21

## 1 Answer

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}$.

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