1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Your statement is not correct, and EXP with oracle in EXP is not equal to EXP. Can you credit the original source? $\endgroup$
    – lox
    Aug 11, 2019 at 18:02
  • $\begingroup$ 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 $\endgroup$
    – fgdhdfg
    Aug 11, 2019 at 18:14
  • 1
    $\begingroup$ Can you name the book title and give the context in which this question appeared? $\endgroup$
    – lox
    Aug 11, 2019 at 18:41
  • $\begingroup$ 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 $\endgroup$
    – fgdhdfg
    Aug 11, 2019 at 18:59
  • $\begingroup$ What about book title? $\endgroup$
    – Evil
    Aug 11, 2019 at 22:36

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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