gegen

Dies ist ein offenes Problem, das unter anderem impliziert . Siehe folgendes Papier: $\mathsf{NP} = \mathsf{RP}$

Alan Selman. Eine Taxonomie von Komplexitätsklassen von Funktionen. Journal of Computer and Systems Sciences 48 (1992), S. 357-381.

Sie können es hier herunterladen : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&rep=rep1&type=pdf

Jan Johannsen
quelle

In diesem Papier , das sie verwenden , um die Klasse

, kann ich davon ausgehen , dass

? Gibt es als Nebenfrage einen prototypischen

-kompletten Satz?

{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

Nebenfrage: Meinen Sie komplette Mengen für

? Die einzige natürliche, die ich kenne, ist die Ermittlung des Siegers einer Dodgson-Wahl (siehe Artikel: E. Hemaspaandra, L. Hemaspaandra und J. Rothe). Genaue Analyse von Dodgson-Wahlen: Lewis Carrolls Wahlsystem von 1876 erschwert den parallelen Zugang zu NP. J. ACM 44 (1997), S. 214-224

P^{N P | |}

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

Jan Johannsen,

Zur ersten Frage: Ich weiß es nicht, aber

, also

impliziert

{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

Eigentlich ist das, wonach ich suche, ein Problem, das für

vollständig ist

, und ich habe noch keinen gefunden.

{F P}^{N P | |}

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

Jorge

gegen

Antworten: