contre

Je sais que (nombre d'appels logarithmiques à l'oracle NP) est équivalent à (polynôme nombre de requêtes parallèles à l’oracle NP). Je me demandais si la version "fonctionnelle" de ces classes était également équivalente, c'est-à-dire si $\mathsf{P}^{\mathsf{NP}[\log n]}$ $\mathsf{P}^{\mathsf{NP}||}$

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

$\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$ Si on sait que c'est vrai, un pointeur serait vraiment utile.

cc.complexity-theory complexity-classes Jorge
la source

Réponses:

C'est un problème ouvert, il implique entre autres . Voir l'article suivant: $\mathsf{NP} = \mathsf{RP}$

Alan Selman. Une taxonomie des classes de complexité des fonctions. Journal of Computer and Systems Sciences 48 (1992), pp. 357-381.

Vous pouvez l'obtenir ici: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&rep=rep1&type=pdf

Jan Johannsen
la source

{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}\|}$

Sur la question secondaire: voulez-vous dire des ensembles complets pour ? Le seul naturel que je connaisse est le calcul du vainqueur d'une élection Dodgson, voir l'article: E. Hemaspaandra, L. Hemaspaandra et J. Rothe. Analyse exacte des élections Dodgson: le système de vote de Lewis Carroll de 1876 est difficile pour un accès parallèle à NP. J.ACM 44 (1997), pp. 214-224

P^{N P | |}

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

Jan Johannsen

Sur la première question: je ne sais pas, mais , donc implique .

{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

En fait, ce que je recherche est un problème complet pour , et je n'en ai pas encore trouvé un.

{F P}^{N P | |}

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

Jorge