World's most popular travel blog for travel bloggers.

# Can we separate P and E?

, ,
Problem Detail:

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

###### Answered By : Yuval Filmus

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.