Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
3  
$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
1  
@YuvalFilmus, he means $O(n^n)$ where $n$ is not constant. –  sxd Feb 15 '12 at 8:35
1  
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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.