<p>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$. <br>
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}$.</p>

CC BY-SA 3.0
2013-08-31T02:50:12.537Z
hi , thank you a lot , could you list references ?
Fayez Abdlrazaq Deab
CC BY-SA 3.0
2013-08-31T03:09:07.880Z
2) L.G. Valiant & V. Vazirani “NP is as easy as detecting Unique Solutions” Theoretical Computer Science 47 (1986) pp. 85-93.
Tayfun Pay
CC BY-SA 3.0
2013-08-31T03:09:27.053Z
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
CC BY-SA 3.0
2013-08-31T03:10:53.763Z
http://cstheory.stackexchange.com/questions/6404/survey-on-p-and-or-counting-problems
Tayfun Pay
CC BY-SA 3.0
2013-08-31T00:38:28.297Z
2013-08-31T03:07:07.967Z
2013-08-31T03:07:07.967Z
Tayfun Pay
<p>I was trying to understand these classes but always got confused ... the questions are : </p>

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

<p>What is the relation of $\oplus P$ and $NP$ ? is this question open ? </p>

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

CC BY-SA 3.0
2013-08-29T00:16:54.437Z
$FNP \subseteq P^{\#P}$, $NP \subseteq RP^{\oplus P}$ and $P^{FNP}$ is contained in Functional Polynomial Hierarchy, which is called $FPH$.
Tayfun Pay
CC BY-SA 3.0
2013-08-29T01:02:23.997Z
@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
CC BY-SA 3.0
2013-08-29T01:21:45.440Z
@Tayfun could you please list the references proving these results.
Fayez Abdlrazaq Deab
CC BY-SA 4.0
2024-05-12T13:00:21.877Z
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$.
plm
<cc.complexity-theory>
$FNP$ ,$ \#P$,$\oplus P$ classes
Fayez Abdlrazaq Deab
# $FNP$ ,$ \#P$,$\oplus P$ classes

(Asked by: username_0 on 2013-08-22)

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 ?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: $FNP \subseteq P^{\#P}$, $NP \subseteq RP^{\oplus P}$ and $P^{FNP}$ is contained in Functional Polynomial Hierarchy, which is called $FPH$.  
> **username_0**: @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 .  
> **username_0**: @Tayfun could you please list the references proving these results.  
> **username_2**: 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$.  

---

## 1 answers

### Answer by username_1 on 2013-08-31. Score: 4 | Accepted 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}$.

> **Comments:**
> **username_0**: hi , thank you a lot , could you list references ?  
> **username_1**: 2) L.G. Valiant & V. Vazirani “NP is as easy as detecting Unique Solutions” Theoretical Computer Science 47 (1986) pp. 85-93.  
> **username_1**: 1)S. Toda, O. Watanabe. “Polynomial-time 1-Turing reductions from #PH to #P.” Theoretical Computer Science. Volume 100. Pages 205-221. 1992.  
> **username_1**: http://cstheory.stackexchange.com/questions/6404/survey-on-p-and-or-counting-problems  

---

