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