How can EXP^P be characterized?

Question

I had a question about EXP^P (EXPTIME with access to a P oracle). I thought I had read somewhere that EXP = EXP^P, and that seemed fairly intuitive to me: I thought "adding polynomial power to something that already has exponential power must not change a lot". Now I am questioning myself: I was searching for something that verified thar EXP equals EXP^P, but I can't find something like that. I am thinking that I probably just assumed those classes were equal and they actually are not (or it is still not known). Does anyone have some hints about how to characterize this class? Or if there is a known relationship between EXP and EXP^P?

Answer 1

You are right, EXP = EXP^P.

Suppose that you have an oracle $f$ that is in $P$. This means that whatever computation the oracle $f$ is doing, can be done by some polynomial-time algorithm, let's call it $B$. Consider any algorithm $A$ in EXP^P that uses the oracle $f$. We can modify $A$ so that any time it would have called $f$, it instead runs the polynomial-time algorithm $B$ (as a subroutine) without using the oracle.

In this way, we have obtained a new algorithm that doesn't use any oracle. What is the running time of this new algorithm? It is at most the running time of $A$, times the running time of $B$, or in other words, at most an exponential function times a polynomial function. One can easily show that this is also an exponential function (for example, $2^x \times x^7 = O(4^x)$, since $x^7 = O(2^x)$). Therefore, we have obtained a new algorithm that also runs in exponential time, and doesn't use an oracle, so this new algorithm must be in EXP.

In this way, we can convert any algorithm in EXP^P to an algorithm in EXP. This shows that every problem in EXP^P is also in EXP. The other direction (every problem in EXP is also in EXP^P) is trivial (just ignore the oracle and never use it), so this shows that EXP = EXP^P.