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
    Yes, NP is contained in EXP. Have a look at the nice Venn diagram [here](http://ocw.mit.edu/courses/mathematics/18-404j-theory-of-computation-fall-2006/).2012-02-15
  • 0
    @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.2012-02-15
  • 3
    $DTIME(O(n^k))$ can't even represent $P$, let alone $NP$, by the time hierarchy theorem.2012-02-15
  • 1
    @YuvalFilmus, he means $O(n^n)$ where $n$ is not constant.2012-02-15
  • 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