Literatur rund um NP vs EXPTIME

Auch wenn es kein entscheidender Punkt ist, sehe ich keine Literatur zu dieser Frage. Gibt es Relativierungsergebnisse?

Wäre es nicht ganz einfach, eine strikte Einbeziehung durch Anpassung des nicht deterministischen Zeithierarchiesatzes zu beweisen, indem alle möglichen Pfade der NP-Maschine untersucht werden?

cc.complexity-theory complexity-classes Ludovic Patey
quelle

Es ist leicht, eine Orakeltrennung zwischen NP und EXP zu beweisen. Es gibt einen nicht deterministischen Zeithierarchiesatz, der besagt, dass NP streng in NEXP enthalten ist. Ich sehe nicht, wie es an NP vs EXP angepasst werden könnte.

Robin Kothari

@Robin Ja, natürlich, ein Oracle , so dass

bedeutet , dass

. Aber da ich kein Orakel finde, bei dem

ist, könnte ein Beweis für

relativieren , wenn dies nicht der Fall ist.

N P^{A} \neq P S P A C E^{A}

$NP^A \neq PSPACE^A$

N P^{A} \neq E X P^{A}

$NP^A \neq EXP^A$

N P^{B} = E X P^{B}

$NP^B = EXP^B$

N P \neq E X P

$NP \neq EXP$

Ludovic Patey

Der Komplexitätszoo ( qwiki.stanford.edu/index.php/Complexity_Zoo ) sagt: ... Es gibt Orakel, zu denen

[Hel84a], [Hel84b], [Kur85], [ Hel86], .... Siehe zum Beispiel Zwei Orakel, die eine große Krise erzwingen ( people.cs.uchicago.edu/~fortnow/papers/nexp.ps )

E X P = N P = Z P P

$EXP = NP = ZPP$

Marzio De Biasi

@Vor, @Robin, ich denke, das sollten Antworten sein

Suresh Venkat

Antworten:

Der Complexity Zoo sagt:

... Es gibt Orakel, zu denen [Hel84a], [Hel84b], [Kur85], [Hel86], .... $EXP=NP=ZPP$

Siehe zum Beispiel Zwei Orakel, die ein großes Knirschen erzwingen .

Vielleicht ist das von Dekhtyar verwendete ursprüngliche Orakel weniger mächtig (und einfacher): Zur Relativierung deterministischer und nichtdeterministischer Komplexitätsklassen in Proc. Mathematische Grundlagen von CS 1977 ... aber ich habe seine Arbeit nicht.

Marzio De Biasi
quelle

Vielen Dank. Der genaue Name der Dekhtyar-Arbeit lautet Über die Relativierung deterministischer und nichtdeterministischer Komplexitätsklassen.

Ludovic Patey