1
$\begingroup$

I'm trying to prove $EXP \subset E^E$ (strictly).

I believe I need to construct my own $A \in E^E$ and show that $A \notin EXP$, but I cannot think of a smart way of doing that.

Thanks.

$\endgroup$

1 Answer 1

2
$\begingroup$

The class $E^E$ contains 2E, which is the class of problems solvable in iterated exponential time. The reason is that the E oracle can be applied on a padded input of exponential size. The time hierarchy theorem separates 2E from EXP.

$\endgroup$
3
  • $\begingroup$ To elaborate, are you saying we can express $E$ in terms of $DTIME(...)$ (i.e without an oracle), and show that it's strictly greater then $EXP=DTIME(2^{n^c})$? Because then, the conclusion comes directly from the time hierarchy theorem. $\endgroup$
    – galah92
    Aug 1, 2018 at 10:20
  • $\begingroup$ Not exactly, though perhaps a more refined statement to that effect might hold. $\endgroup$ Aug 1, 2018 at 10:42
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – galah92
    Aug 1, 2018 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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