si P=NP, entonces es E=NE?

Question

Si la complejidad computacional de la clase P es igual a NP, ¿la complejidad de la clase E igual a la clase de NE?

E se define como el $DTIME(O(2^{O(n)}))$ NE se define como $NTIME(O(2^{O(n)}))$

Muchas gracias.

Answer 1

Sí, mediante el relleno de argumento. El artículo de Wikipedia sobre el relleno argumento contiene una prueba de la implicación P=NP ⇒ EXP=NEXP, y la implicación P=NP ⇒ E=NE puede ser probado de la misma manera. Os dejo los detalles como ejercicio.