5
$\begingroup$

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?

  • 1
    Well, it is known that $NP \subset EXP$, since you can go over all possible witnesses in time $\tilde{O}(2^{n^k})$.2012-02-17

1 Answers 1

3

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$.