Литература вокруг NP против EXPTIME

Даже если это не решающий момент, я не вижу литературы по этому вопросу. Есть ли результаты релятивизации?

Разве не было бы достаточно просто доказать строгое включение путем адаптации недетерминированной теоремы иерархии времени, исследуя все возможные пути машины NP?

cc.complexity-theory complexity-classes Людовик Патей
источник

Легко доказать разделение оракула между NP и EXP. Есть недетерминированная теорема иерархии времени, которая говорит нам, что NP строго содержится в NEXP. Я не понимаю, как это может быть адаптировано к NP против EXP.

Робин Котари

@Robin Да, конечно, оракул такой, что

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$ может быть релятивизирует.

Людовик Патей

Зоопарк Сложности ( qwiki.stanford.edu/index.php/Complexity_Zoo ) говорит: ... Существуют оракулы, относительно которых

E X P = N P = Z P P

$EXP = NP = ZPP$ [Hel84a], [Hel84b], [Kur85], [Hel86], .... Смотрите, например, Два оракула, которые вызывают большой кризис ( people.cs.uchicago.edu/~fortnow/papers/nexp.ps )

Марцио Де Биаси

@Vor, @Robin, я думаю, что это должны быть ответы

Суреш Венкат

Ответы:

Сложность зоопарк говорит:

... Существуют оракулы, относительно которых $EXP=NP=ZPP$ [Hel84a], [Hel84b], [Kur85], [Hel86], ....

Посмотрите, например, Два оракула, которые вызывают большой кризис .

Возможно, оригинальный оракул, используемый Дехтярем, менее мощный (и более простой): о релятивизации классов детерминированной и недетерминированной сложности в Proc. Математические основы CS 1977 ... но у меня нет его работы.

Марцио де Биаси
источник

Спасибо. Точное название дехтярской статьи: «О релятивизации детерминированных и недетерминированных классов сложности».

Людовик Патей