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

Question

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 00: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 01:02
@Tayfun could you please list the references proving these results. — Fayez Abdlrazaq Deab, Aug 29 '13 at 01:21

Tayfun Pay · Accepted Answer · 2013-08-31T03:07:07.967

4

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

edited Aug 31 '13 at 03:07

answered Aug 31 '13 at 00:38

Tayfun Pay

2,598
2
18
45

hi , thank you a lot , could you list references ? – Fayez Abdlrazaq Deab Aug 31 '13 at 02:50
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 03: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 03:09

http://cstheory.stackexchange.com/questions/6404/survey-on-p-and-or-counting-problems – Tayfun Pay Aug 31 '13 at 03:10

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

1 Answers1