kontra

Wiem, że $\mathsf{P}^{\mathsf{NP}[\log n]}$ (logarytmicznie wiele wywołań do NP oracle) jest równoważne $\mathsf{P}^{\mathsf{NP}||}$ (wielomianowa liczba równoległych zapytań do NP oracle). Zastanawiałem się, czy wersja „funkcyjna” tych klas również jest równoważna, to znaczy czy

Jeśli wiadomo, że to prawda, wskaźnik byłby naprawdę pomocny.

{F P}^{N P [\log n]} = {F P}^{N P | |}

$\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$

cc.complexity-theory complexity-classes

— Jorge
źródło

Jest to problem otwarty, implikuje między innymi Zobacz następujący artykuł: $\mathsf{NP} = \mathsf{RP}$

Alan Selman. Taksonomia złożoności Klasy funkcji. Journal of Computer and Systems Sciences 48 (1992), s. 357-381.

Możesz go pobrać tutaj: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&rep=rep1&type=pdf

— Jan Johannsen
źródło

W tym artykule używają klasy

, czy mogę założyć, że

? jako pytanie poboczne, czy istnieje prototypowy zestaw

{F P}_{t t}^{N P}

$\mathsf{FP}^{\mathsf{NP}}_{tt}$

{F P}_{t t}^{N P} = {F P}^{N P ‖}

$\mathsf{FP}^{\mathsf{NP}}_{tt}=\mathsf{FP}^{\mathsf{NP}\|}$

{F P}^{N P ‖}

$\mathsf{FP}^{\mathsf{NP}\|}$

— Jorge

Na pytanie boczne: Czy masz na myśli kompletne zestawy dla

? Jedyny naturalny, jaki znam, to wyłonienie zwycięzcy w wyborach Dodgsona, patrz artykuł: E. Hemaspaandra, L. Hemaspaandra i J. Rothe. Dokładna analiza wyborów Dodgsona: System głosowania Lewisa Carrolla z 1876 r. Jest trudny do równoległego dostępu do NP. J.ACM 44 (1997), s. 214–224

P^{N P | |}

$\mathsf{P}^{\mathsf{NP}||}$

— Jan Johannsen,

Na pierwsze pytanie: nie wiem, ale

, dlatego

oznacza

{F P}^{N P [\log n]} \subseteq {F P}_{t t}^{N P} \subseteq {F P}^{N P | |}

$\mathsf{FP}^{\mathsf{NP}[\log n]} \subseteq \mathsf{FP}_{tt}^{\mathsf{NP}} \subseteq \mathsf{FP}^{\mathsf{NP}||}$

{F P}^{N P [\log n]} = {F P}^{N P | |}

$\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$

{F P}^{N P [\log n]} = {F P}_{t t}^{N P}

$\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}_{tt}^{\mathsf{NP}}$

— Jan Johannsen

Właściwie to, czego szukam, to kompletny problem dla

i jeszcze go nie znalazłem.

{F P}^{N P | |}

$\mathsf{FP}^{\mathsf{NP}||}$

— Jorge