,

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

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

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

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

cc.complexity-theory

jest zawarty funkcjonalnych Wielomian hierarchii, zwanego

F N P \subseteq P^{# P}

$FNP \subseteq P^{\#P}$

N P \subseteq R P^{\oplus P}

$NP \subseteq RP^{\oplus P}$

P^{F N P}

$P^{FNP}$

F P H

$FPH$

— Tayfun Pay

@Tayfun, coś nie ma sensu:

pierwsza to klasa funkcji, a druga to klasa problemów decyzyjnych.

F N P \subseteq P^{# P}

$FNP\subseteq P^{\#P}$

— Fayez Abdlrazaq Deab

@Tayfun, czy możesz wymienić referencje potwierdzające te wyniki.

— Fayez Abdlrazaq Deab

1) jest zawarte w , który nazywany jest „funkcjonalny wielomian hierarchia”, w którym każda funkcja w jest wielomianem czas 1 Turinga reduciable do pewnego funkcjonowania w . 2) Wiemy z twierdzeniem Bitny Vazirani że . Wiemy również, że . Dlatego mamy $\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}$

— Tayfun Pay
źródło

cześć, dziękuję bardzo, czy mógłbyś wymienić referencje?

— Fayez Abdlrazaq Deab

2) LG Valiant i V. Vazirani „NP jest tak łatwe, jak wykrywanie unikalnych rozwiązań” Theoretical Computer Science 47 (1986) str. 85-93.

— Tayfun Zapłać

1) S. Toda, O. Watanabe. „Redukcje 1-Turinga w czasie wielomianowym z #PH do #P.” Informatyka teoretyczna. Tom 100. Strony 205-221. 1992.

— Tayfun Pay

cstheory.stackexchange.com/questions/6404/…

— Tayfun Pay