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

  • 2
    $\begingroup$ 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. $\endgroup$
    – alsips-cl
    Commented Dec 20, 2023 at 17:10

1 Answer 1


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$.

  • $\begingroup$ Oh brilliant, thank you for this answer! $\endgroup$
    – Meki21
    Commented Dec 19, 2023 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.