2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.