<p>The known separation <span class="math-container">$\mathbf{P} \neq \mathbf{EXP}$</span> is a <em>relativizing</em> result, meaning that it works even in the presence of oracles i.e., it holds that for every oracle <span class="math-container">$O$</span>, <span class="math-container">$\mathbf{P}^O \neq \mathbf{EXP}^O$</span>. One way to see this is that the Time Hierarchy Theorem, from which one can derive  <span class="math-container">$\mathbf{P} \neq \mathbf{EXP}$</span>, can be proved in the presence of an arbitrary oracle. Essentially, the argument is so abstract and general and treats the machines as black boxes that it does not matter too much whether an oracle is present or not. You can see, for example, Sections 3.1 and 3.4 in Arora-Barak for full proofs on this.</p>
<p>As to your intuition involving an <span class="math-container">$\mathbf{EXP}$</span>-complete language as an oracle, it might help to note that a language <span class="math-container">$A$</span> may be <span class="math-container">$\mathbf{EXP}$</span>-complete, but not <span class="math-container">$\mathbf{EXP}^A$</span>-complete, which is what you would need to show that <span class="math-container">$\mathbf{EXP}^A \subseteq \mathbf{P}^A$</span>.</p>

CC BY-SA 4.0
2023-12-19T12:59:26.193Z
Oh brilliant, thank you for this answer!
Meki21
CC BY-SA 4.0
2023-12-19T12:40:30.833Z
2023-12-19T12:40:30.833Z
Noel Arteche
<p>I have been trying to find an argument, but with no success so far.</p>
<p>My understanding is that if I can choose <span class="math-container">$A$</span> to be an <span class="math-container">$EXP-complete$</span> language, then I can simply reduce any other problem to that and query the oracle f</p>

CC BY-SA 4.0
2023-12-20T17:10:48.333Z
One key issue here is that an $\mathbf{EXP}^{\mathbf{EXP}}$ machine can simulate as much as $2^{2^{poly(n)}}$ steps of a $\mathbf{P}$ machine, not just $2^{poly(n)}$. Could be an intuitive way of seeing the separation.
alsips-cl
<oracles>
Why does there not exist an oracle $A$ such that $EXP^{A} = P^{A}$?
Meki21
# Why does there not exist an oracle $A$ such that $EXP^{A} = P^{A}$?

(Asked by: username_0 on 2023-12-19)

I have been trying to find an argument, but with no success so far.

My understanding is that if I can choose $A$ to be an $EXP-complete$ language, then I can simply reduce any other problem to that and query the oracle f

**Tags:** oracles

> **Comments:**
> **username_1**: One key issue here is that an $\mathbf{EXP}^{\mathbf{EXP}}$ machine can simulate as much as $2^{2^{poly(n)}}$ steps of a $\mathbf{P}$ machine, not just $2^{poly(n)}$. Could be an intuitive way of seeing the separation.  

---

## 1 answers

### Answer by username_2 on 2023-12-19. Score: 5 | Accepted answer

The known separation $\mathbf{P} \neq \mathbf{EXP}$ is a *relativizing* result, meaning that it works even in the presence of oracles i.e., it holds that for every oracle $O$, $\mathbf{P}^O \neq \mathbf{EXP}^O$. One way to see this is that the Time Hierarchy Theorem, from which one can derive $\mathbf{P} \neq \mathbf{EXP}$, can be proved in the presence of an arbitrary oracle. Essentially, the argument is so abstract and general and treats the machines as black boxes that it does not matter too much whether an oracle is present or not. You can see, for example, Sections 3.1 and 3.4 in Arora-Barak for full proofs on this.

As to your intuition involving an $\mathbf{EXP}$-complete language as an oracle, it might help to note that a language $A$ may be $\mathbf{EXP}$-complete, but not $\mathbf{EXP}^A$-complete, which is what you would need to show that $\mathbf{EXP}^A \subseteq \mathbf{P}^A$.

> **Comments:**
> **username_0**: Oh brilliant, thank you for this answer!  

---

