Littérature autour de NP vs EXPTIME

Même si ce n'est pas un point crucial, je ne vois aucune littérature autour de cette question. Y a-t-il des résultats de relativisation?

Ne serait-il pas assez simple de prouver une inclusion stricte en adaptant le théorème de la hiérarchie temporelle non déterministe en explorant tous les chemins possibles de la machine NP?

cc.complexity-theory complexity-classes Ludovic Patey
la source

Il est facile de prouver une séparation oracle entre NP et EXP. Il existe un théorème de hiérarchie temporelle non déterministe qui nous dit que NP est strictement contenu dans NEXP. Je ne vois pas comment il pourrait être adapté à NP vs EXP.

Robin Kothari

@Robin Oui, bien sûr, un oracle tel que

implique que

. Mais comme je ne trouve pas d'oracle tel que

, alors s'il n'y en a pas, une preuve de

pourrait être relativisante.

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

Le Complexity Zoo ( qwiki.stanford.edu/index.php/Complexity_Zoo ) dit: ... Il existe des oracles par rapport auxquels

[Hel84a], [Hel84b], [Kur85], [ Hel86], .... Voir par exemple Deux oracles qui forcent un gros resserrement ( people.cs.uchicago.edu/~fortnow/papers/nexp.ps )

E X P = N P = Z P P

$EXP = NP = ZPP$

Marzio De Biasi

@Vor, @Robin, je pense que ce devraient être des réponses

Suresh Venkat

Réponses:

Le Complexity Zoo dit:

... Il existe des oracles par rapport auxquels [Hel84a], [Hel84b], [Kur85], [Hel86], .... $EXP=NP=ZPP$

Voir par exemple Deux oracles qui forcent un gros crunch .

L'oracle original utilisé par Dekhtyar est peut-être moins puissant (et plus simple): sur la relativisation des classes de complexité déterministes et non déterministes dans Proc. Fondements mathématiques de CS 1977 ... mais je n'ai pas son papier.

Marzio De Biasi
la source

Je vous remercie. Le nom exact de l'article de Dekhtyar est Sur la relativisation des classes de complexité déterministes et non déterministes.

Ludovic Patey