Komplexitätsklasse NEXP

11

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

Ist etwas über NEXP NP bekannt ? Ist es gleich NEXP oder einer anderen Klasse? Gibt es andere als die generischen Probleme ( akzeptiert eine NEXP NP- Maschine und ein Wort?).NPNP

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 Σ 2 E X P . NEXPNPΣ2EXP
Ryan Williams

Antworten:

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 .NEXPNP

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 N E X P N P enthalten .NEXPNPNEXPNP

domotorp
quelle
NEXPEXPNEXPNPPNP
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
NEXPNPNEXPEXP=NEXPEXPEXP
DTIME(2n)DTIME(2n)=DTIME(22n)
f(n)DTIME(f(n))P/poly
3

NPPNENENEXPNP

5501
quelle
1

NEXPNPpoly(2nk)=O(2nk+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
NPNPNP
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