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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.