Literatura em torno de NP vs EXPTIME

9

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?

Ludovic Patey
fonte
2
É 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
2
@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. NPAPSPACEANPAEXPANPB=EXPBNPEXP
Ludovic Patey
3
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 )EXP=NP=ZPP
Marzio De Biasi
@Vor, @Robin, acho que estas devem ser respostas
Suresh Venkat

Respostas:

10

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