Literatura wokół NP vs EXPTIME

Nawet jeśli nie jest to kluczowa kwestia, nie widzę żadnej literatury wokół tego pytania. Czy są wyniki relatywizacji?

Czy nie byłoby łatwo udowodnić ścisłe włączenie poprzez dostosowanie niedeterministycznego twierdzenia o hierarchii czasu poprzez badanie wszystkich możliwych ścieżek maszyny NP?

cc.complexity-theory complexity-classes Ludovic Patey
źródło

Łatwo jest udowodnić separację wyroczni między NP a EXP. Istnieje niedeterministyczne twierdzenie o hierarchii czasu, które mówi nam, że NP jest ściśle zawarty w NEXP. Nie rozumiem, jak można go dostosować do NP vs. EXP.

Robin Kothari,

@Robin Tak, oczywiście, że takie wyroczni oznacza, że . Ale ponieważ nie znajduję takiej wyroczni, że , to jeśli nie, dowód może być relatywizujący.

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

Zoo Złożoność ( qwiki.stanford.edu/index.php/Complexity_Zoo ) mówi: ... Istnieją wyrocznie, w stosunku do których [Hel84a], [Hel84b], [Kur85], [Hel86], .. .. Zobacz na przykład Dwie wyrocznie, które wymuszają wielki kryzys ( people.cs.uchicago.edu/~fortnow/papers/nex.ps )

E X P = N P = Z P P

$EXP = NP = ZPP$

Marzio De Biasi

@Vor, @Robin, myślę, że powinny to być odpowiedzi

Suresh Venkat

Odpowiedzi:

Złożoność Zoo mówi:

... Istnieją wyrocznie, w stosunku do których [Hel84a], [Hel84b], [Kur85], [Hel86], .... $EXP=NP=ZPP$

Zobacz na przykład dwie wyrocznie, które wymuszają wielki kryzys .

Być może oryginalna wyrocznia używana przez Dekhtyara jest mniej potężna (i prostsza): w sprawie relatywizacji deterministycznych i niedeterministycznych klas złożoności w Proc. Podstawy matematyczne CS 1977 ... ale nie mam jego pracy.

Marzio De Biasi
źródło

Dziękuję Ci. Dokładna nazwa referatu Dekhtyar brzmi: Relatywizacja deterministycznych i niedeterministycznych klas złożoności.

Ludovic Patey