,

Próbowałem zrozumieć te zajęcia, ale zawsze byłem zdezorientowany ... pytania są następujące:

Jaki jest związek między a # P , w szczególności czy jest to pytanie otwarte?$FNP$$\#P$

Jaki jest stosunek i N P ? czy to pytanie jest otwarte?$\oplus P$$NP$

A co z relacją między a P F N P ? czy to pytanie jest otwarte?$PH$$P^{FNP}$

1) jest zawarte w F p H , który nazywany jest „funkcjonalny wielomian hierarchia”, w którym każda funkcja w F p H jest wielomianem czas 1 Turinga reduciable do pewnego funkcjonowania w # P . 2) Wiemy z twierdzeniem Bitny Vazirani że N P ⊆ R P P r O m i e e u P . Wiemy również, że U P ⊆ ⊕ P . Dlatego mamy 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}$