1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – D.W.
    Mar 13 at 19:13
  • $\begingroup$ Thanks for your help! I will ask the second question separately as you suggest. $\endgroup$ Mar 14 at 14:55

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Since the algorithm runs in exponential time, the inputs to the oracle can have exponential length. The proof still works, though. $\endgroup$ Mar 13 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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