# Does EXP^EXP = EXP? [duplicate]

Does $$\mathrm{EXP}^\mathrm{EXP}=\mathrm{EXP}$$?

Here is my thought: $$\mathrm{EXP}$$ machine can ask $$2^{O(n)}$$ queries to the oracle, and each oracle would itself solve an exponential time problem in a single step. So the total power would be $$2^{O(n)}\times2^{O(n)}$$ which would still be in EXP.

• Your statement is not correct, and EXP with oracle in EXP is not equal to EXP. Can you credit the original source?
– lox
Aug 11, 2019 at 18:02
• Do you have a proof or any idea why the the statement is not correct?This is an question from a book I am reading and the original question did not implement that the classes are equal.Sorry for the misunderstanding. @lox Aug 11, 2019 at 18:14
• Can you name the book title and give the context in which this question appeared?
– lox
Aug 11, 2019 at 18:41
• I am copying the question from the book:"Show that EXP with oracle in EXP is not equal to EXP".I got the thought and posted it up their (posting wrong answer in the internet gets more attention) . Pay attention that In my question I did not state that they are equal. @lox Aug 11, 2019 at 18:59
– Evil
Aug 11, 2019 at 22:36

Your definition of EXP is a bit off (you're thinking of $$\textbf{E} = \textbf{DTIME}(2^{O(n)})$$ instead of $$\textbf{EXP} = \textbf{DTIME}(2^{n^{O(1)}})$$), but either way the assertion that "each oracle would itself solve an exponential time problem in a single step" is false.

This is because, given exponential time, the machine can write (say) $$2^n$$ bits to the oracle's input tape, at which point the oracle is allowed to run exponential-time algorithms as measured relative to the size of the $$2^n$$ bit input (and therefore doubly-exponential in $$n$$). Thus, just by padding the input to an exponential size and calling the oracle once, you can solve any problem in 2EXP, violating the time hierarchy.