Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to know any relationship between the complexity class E(and EXP) and NP.

I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size of input, and k is constant.

edit: for example, is NP contained in EXP?

share|cite|improve this question
Yes, NP is contained in EXP. Have a look at the nice Venn diagram here. – William DeMeo Feb 15 '12 at 6:38
@williamdemeo Thank you very much. Can you also help me here: I also would like to know whether $DTIME(O(n^n))$ can represent NP. thank you so much. – user24996 Feb 15 '12 at 6:48
$DTIME(O(n^k))$ can't even represent $P$, let alone $NP$, by the time hierarchy theorem. – Yuval Filmus Feb 15 '12 at 7:38
@YuvalFilmus, he means $O(n^n)$ where $n$ is not constant. – sxd Feb 15 '12 at 8:35
Well, it is known that $NP \subset EXP$, since you can go over all possible witnesses in time $\tilde{O}(2^{n^k})$. – Yuval Filmus Feb 17 '12 at 7:27

We have:

$$ P \subseteq NP \subseteq PSPACE \subseteq EXP \,, $$

and $P \subsetneq EXP$. The latter is the result of time-hierarchy theorem; see here. Therefore, at least one of the inclusions above is strict, but no one knows which.

Furthermore, we know from Ronald V. Book's 1972 paper that $E \ne NP$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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