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$
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$
  • $\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 '18 at 10:20
  • $\begingroup$ Not exactly, though perhaps a more refined statement to that effect might hold. $\endgroup$ – Yuval Filmus Aug 1 '18 at 10:42
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – galah92 Aug 1 '18 at 12:59

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.