<p>The <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#exp" rel="nofollow">Complexity Zoo</a> says: </p>

<p>... There exist oracles relative to which $EXP=NP=ZPP$ [Hel84a], [Hel84b], [Kur85], [Hel86],....</p>

<p>See for example <a href="http://people.cs.uchicago.edu/~fortnow/papers/nexp.ps" rel="nofollow">Two oracles that force a big crunch</a>.</p>

<p>Perhaps the original oracle used by Dekhtyar is <em>less powerful</em> (and simpler): <em>On the relativization of deterministic and nondeterministic complexity classes</em> in <em>Proc. Mathematical Foundations of CS</em> 1977 ... but I don't have his paper.</p>

CC BY-SA 3.0
2011-05-11T22:53:42.690Z
Thank you. The exact name of Dekhtyar paper is On the relativization of deterministic and nondeterministic complexity classes.
Ludovic Patey
CC BY-SA 3.0
2011-05-11T17:40:28.350Z
2015-09-09T14:52:44.710Z
2015-09-09T14:52:44.710Z
Marzio De Biasi
<p>Even if it isn't a crucial point, I don't see any literature around this question. Are there relativisation results ?</p>

<p>Wouldn't it be quite straightforward to prove strict inclusion by adapting non-deterministic time hierarchy theorem by exploring all possible paths of the NP machine ?</p>

CC BY-SA 3.0
2011-05-11T12:47:21.153Z
It's easy to prove an oracle separation between NP and EXP. There is a non-deterministic time hierarchy theorem which tells us that NP is strictly contained in NEXP. I don't see how it could be adapted to NP vs EXP.
Robin Kothari
CC BY-SA 3.0
2011-05-11T13:22:59.790Z
@Robin Yes, of course, an oracle such that $NP^A \neq PSPACE^A$ implies that $NP^A \neq EXP^A$. But as I don't find oracle such that $NP^B = EXP^B$, then if there isn't, a proof of $NP \neq EXP$ could be relativizing.
Ludovic Patey
CC BY-SA 3.0
2011-05-11T17:33:05.090Z
The Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo) says:
... There exist oracles relative to which $EXP = NP = ZPP$ [Hel84a], [Hel84b], [Kur85], [Hel86],.... See for example *Two oracles that force a big crunch* (http://people.cs.uchicago.edu/~fortnow/papers/nexp.ps)
Marzio De Biasi
CC BY-SA 3.0
2011-05-11T17:33:58.680Z
@Vor, @Robin, I think these should be answers
Suresh Venkat
<cc.complexity-theory><complexity-classes>
Literature around NP vs EXPTIME
Ludovic Patey
# Literature around NP vs EXPTIME

(Asked by: username_0 on 2011-05-11)

Even if it isn't a crucial point, I don't see any literature around this question. Are there relativisation results ?

Wouldn't it be quite straightforward to prove strict inclusion by adapting non-deterministic time hierarchy theorem by exploring all possible paths of the NP machine ?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: It's easy to prove an oracle separation between NP and EXP. There is a non-deterministic time hierarchy theorem which tells us that NP is strictly contained in NEXP. I don't see how it could be adapted to NP vs EXP.  
> **username_0**: @Robin Yes, of course, an oracle such that $NP^A \neq PSPACE^A$ implies that $NP^A \neq EXP^A$. But as I don't find oracle such that $NP^B = EXP^B$, then if there isn't, a proof of $NP \neq EXP$ could be relativizing.  
> **username_2**: The Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo) says: ... There exist oracles relative to which $EXP = NP = ZPP$ [Hel84a], [Hel84b], [Kur85], [Hel86],.... See for example *Two oracles that force a big crunch* (http://people.cs.uchicago.edu/~fortnow/papers/nexp.ps)  
> **username_3**: @Vor, @Robin, I think these should be answers  

---

## 1 answers

### Answer by username_2 on 2011-05-11. Score: 10 | Accepted answer

The [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#exp) says:

... There exist oracles relative to which $EXP=NP=ZPP$ [Hel84a], [Hel84b], [Kur85], [Hel86],....

See for example [Two oracles that force a big crunch](http://people.cs.uchicago.edu/~fortnow/papers/nexp.ps).

Perhaps the original oracle used by Dekhtyar is *less powerful* (and simpler): *On the relativization of deterministic and nondeterministic complexity classes* in *Proc. Mathematical Foundations of CS* 1977 ... but I don't have his paper.

> **Comments:**
> **username_0**: Thank you. The exact name of Dekhtyar paper is On the relativization of deterministic and nondeterministic complexity classes.  

---

