Literatura em torno de NP vs EXPTIME

Mesmo que não seja um ponto crucial, não vejo nenhuma literatura em torno dessa questão. Existem resultados de relativização?

Não seria bem simples provar inclusão estrita, adaptando o teorema da hierarquia de tempo não determinístico, explorando todos os caminhos possíveis da máquina NP?

cc.complexity-theory complexity-classes Ludovic Patey
fonte

É fácil provar uma separação do oráculo entre NP e EXP. Existe um teorema da hierarquia de tempo não determinístico que nos diz que NP está estritamente contido no NEXP. Não vejo como isso poderia ser adaptado ao NP vs EXP.

Robin Kothari

@Robin Sim, claro, um oráculo de tal forma que implica que . Mas como não encontro um oráculo de tal forma que , se não houver, uma prova de pode ser relativizada.

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

O Zoológico da Complexidade ( qwiki.stanford.edu/index.php/Complexity_Zoo ) diz: ... Existem oráculos relativos aos quais [Hel84a], [Hel84b], [Kur85], [Hel86], .. .. Veja, por exemplo, dois oráculos que forçam uma grande crise ( people.cs.uchicago.edu/~fortnow/papers/nexp.ps )

E X P = N P = Z P P

$EXP = NP = ZPP$

Marzio De Biasi

@Vor, @Robin, acho que estas devem ser respostas

Suresh Venkat

Respostas:

O zoológico Complexity diz:

... Existem oráculos relativos aos quais [Hel84a], [Hel84b], [Kur85], [Hel86], .... $EXP=NP=ZPP$

Veja, por exemplo, dois oráculos que forçam uma grande crise .

Talvez o oráculo original usado por Dekhtyar seja menos poderoso (e mais simples): sobre a relativização das classes de complexidade determinística e não determinística no Proc. Fundamentos matemáticos do CS 1977 ... mas eu não tenho o trabalho dele.

Marzio De Biasi
fonte

Obrigado. O nome exato do artigo de Dekhtyar é Sobre a relativização de classes de complexidade determinística e não determinística.

Ludovic Patey