Komplexitätsklasse NEXP

11

Ich habe ein Problem, das sich in NEXP und auch durch ein alternierendes TM mit exponentieller Zeit und nur einem Wechsel (beginnend in einem existenziellen Zustand) gelöst werden kann. $^{\text{NP}}$

Ist etwas über NEXP ? Ist es gleich NEXP oder einer anderen Klasse? Gibt es andere als die generischen Probleme ( akzeptiert eine NEXP Maschine und ein Wort?). $^{\text{NP}}$ $^{\text{NP}}$

cc.complexity-theory reference-request complexity-classes nexp Hsien-Chih Chang 張顯之
quelle

2

Schauen Sie sich die Arbeit an der exponentiellen Zeithierarchie an, zum Beispiel ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf

5501

3

Beachten Sie, dass

hat einen anderen Namen in der Literatur (basierend auf den Wechsel Charakterisierung), nämlich

.

N E X P^{N P}

$NEXP^{NP}$

Σ_{2} E X P

$\Sigma_2 EXP$

Ryan Williams

7

Ein natürliches -komplette Problem ist die Entscheidung , einen Satzes von Presburger Arithmetik mit einer -quantifier Präfix (wie gezeigt hier ). Weitere vollständige Probleme im Zusammenhang mit der Datenbanktheorie wurden hier untersucht . $\text{NEXP}^{\text{NP}}$ $\exists^*\forall^*\exists^*$

Christoph Haase
quelle

5

ist (wahrscheinlich) größer als NEXP, da wir dem Orakel Fragen von exponentieller Länge stellen können. Dieser NP in der Macht ist dort praktisch ein NEXP, also z. co-NEXP ist in . $NEXP^{NP}$ $NEXP^{NP}$

domotorp
quelle

N E X P^{E X P}

$NEXP^{EXP}$

N E X P

$NEXP$

N P^{P}

$NP^P$

N P

$NP$

7

@ Huck Polynome werden unter Polynomen geschlossen. Exponentiale sind nicht. Ich kann dem EXP-Orakel also ein exponentiell langes Argument zuführen, und es kann in diesem Argument exponentiell arbeiten, was im ursprünglichen Problem doppelt exponentiell ist.

Mark Reitblatt

N E X P^{N P} \subseteq N E X P^{E X P} = N E X P

$NEXP^{NP}\subseteq NEXP^{EXP}=NEXP$

E X P^{E X P}

$EXP^{EXP}$

D T I M E (2^{n})^{D T I M E (2^{n})} = D T I M E (2^{2^{n}})

$DTIME(2^n)^{DTIME(2^n)}=DTIME(2^{2^{n}})$

f (n)

$f(n)$

D T I M E (f (n)) \subset P / p o l y

$DTIME(f(n))\subset P/poly$

3

$NP$ $P^{NE}$ $NE$ $NEXP^{NP}$

5501
quelle

1

$NEXP^{NP}$ $poly(2^{n^k})=O(2^{n^{k+1}})$ $NEXP$

Für Klammern bearbeitet ...

Aubrey da Cunha
quelle

3

NTMs funktionieren so nicht ganz. NTMs teilen sich, und wenn eine Kopie akzeptiert, akzeptiert das Ganze. Wenn Sie teilen, können Sie die Ergebnisse Ihrer nicht det-Kopien nicht anzeigen. Wenn ich also eine Anfrage an eine NP-Maschine stellen und sofort die entgegengesetzte Antwort zurückgeben würde, wie würden Sie das simulieren?

Mark Reitblatt

1

N P^{N P}

$NP^{NP}$

N P

$NP$

Ah ja. Wenn bei der Simulation einer Orakelabfrage das richtige Ergebnis Nein lautet, geben alle Zweige Nein zurück. Wenn andererseits das richtige Ergebnis Ja lautet, gibt mindestens ein Zweig Ja zurück. Insbesondere können einige Nr. Zurückgeben. Wenn Sie also, wie @Mark vorschlägt, das Ergebnis der Abfrage negieren, erhalten Sie wahrscheinlich falsch positive Ergebnisse.

Aubrey da Cunha

Komplexitätsklasse NEXP

Antworten: