Literatura sobre NP vs EXPTIME

Incluso si no es un punto crucial, no veo ninguna literatura sobre esta cuestión. ¿Hay resultados de relativización?

¿No sería bastante sencillo demostrar una inclusión estricta adaptando el teorema de la jerarquía de tiempo no determinista explorando todos los caminos posibles de la máquina NP?

cc.complexity-theory complexity-classes Patedo Ludovic
fuente

Es fácil demostrar una separación de oráculo entre NP y EXP. Existe un teorema de jerarquía de tiempo no determinista que nos dice que NP está estrictamente contenido en NEXP. No veo cómo podría adaptarse a NP vs EXP.

Robin Kothari

@Robin Sí, por supuesto, un oráculo de tal manera que

implica que

. Pero como no encuentro un oráculo tal que

, entonces, si no lo hay, una prueba de

podría ser relativizante.

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

El complejo zoológico ( qwiki.stanford.edu/index.php/Complexity_Zoo ) dice: ... Existen oráculos en relación con los cuales

[Hel84a], [Hel84b], [Kur85], [ Hel86], .... Ver por ejemplo Dos oráculos que fuerzan una gran crisis ( people.cs.uchicago.edu/~fortnow/papers/nexp.ps )

E X P = N P = Z P P

$EXP = NP = ZPP$

Marzio De Biasi

@Vor, @Robin, creo que estas deberían ser respuestas

Suresh Venkat

Respuestas:

El complejo zoológico dice:

... Existen oráculos con respecto a los cuales [Hel84a], [Hel84b], [Kur85], [Hel86], .... $EXP=NP=ZPP$

Ver, por ejemplo, dos oráculos que fuerzan una gran contracción .

Quizás el oráculo original utilizado por Dekhtyar es menos poderoso (y más simple): sobre la relativización de las clases de complejidad deterministas y no deterministas en Proc. Fundamentos matemáticos de CS 1977 ... pero no tengo su trabajo.

Marzio De Biasi
fuente

Gracias. El nombre exacto del artículo de Dekhtyar es Sobre la relativización de las clases de complejidad deterministas y no deterministas.

Ludovic Patey