,

Saya mencoba memahami kelas-kelas ini tetapi selalu bingung ... pertanyaannya adalah:

Apa hubungan antara dan # P , khususnya apakah ini merupakan pertanyaan terbuka?$FNP$$\#P$

Apa hubungan dan N P ? apakah pertanyaan ini terbuka?$\oplus P$$NP$

Bagaimana dengan hubungan antara dan P F N P ? apakah pertanyaan ini terbuka?$PH$$P^{FNP}$

1) yang terkandung dalam F P H , yang disebut "fungsional polinomial hirarki", di mana setiap fungsi di F P H adalah polinomial waktu 1-Turing reduciable untuk beberapa fungsi dalam # P . 2) Kita tahu dari teorema Valiant Vazirani bahwa N P ⊆ R P P r o m i s e U P . Kita juga tahu bahwa U P ⊆ ⊕ P . Oleh karena itu, kami memiliki N P ⊆ R $\bf FNP$$\bf FPH$$\bf FPH$$\bf \#P$
$\bf NP$ $\subseteq$ $\bf RP^{PromiseUP}$$\bf UP$ $\subseteq$ $\bf \oplus P$$\bf NP$ $\subseteq$ .$\bf RP^{\bf \oplus P}$