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

If the computational complexity class P equals to NP, does the complexity class E equal to the class NE?

E is defined as $DTIME(O(2^{O(n)}))$ NE is defined as $NTIME(O(2^{O(n)}))$

Thank you very much.

share|cite|improve this question

Yes, by using the padding argument. The Wikipedia article on the padding argument contains a proof of the implication P=NP ⇒ EXP=NEXP, and the implication P=NP ⇒ E=NE can be proved in the same way. I leave the details as an exercise.

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.