# How can EXP^P be characterized?

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?

• Please ask only one question per post. I suggest asking your second question separately. I've edited that one out, and you can ask it in a separate post. Thank you, and welcome to CS.SE!
– D.W.
Mar 13 at 19:13
• Thanks for your help! I will ask the second question separately as you suggest. Mar 14 at 14:55

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.