# Can we separate P and E?

Let $\mathsf E$ be deterministic exponential time with linear exponent. Do we know that the inclusion $\mathsf P\subseteq\mathsf E$ is strict? If so, what's the proof?

The time hierarchy immediately separates, for instance, $\mathsf E$ and $\mathsf{TIME}(2^{n\log n})$. Diagonalizing directly on $\mathsf P$ yields essentially the same bound (because diagonalizing polynomials gives $n^n=2^{n\log n}$). But none of this yields a linear exponential upper bound...

Hint: The time hierarchy theorem implies that there is a function $g$ solvable in time $f(n) = n^{\log n}$ but not in time $o(f(n)/\log f(n)) = o(n^{\log n}/\log^2 n)$. In particular, $g$ cannot be solved in polynomial time.