World's most popular travel blog for travel bloggers.

Can we separate P and E?

, , No Comments
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...

Asked By : Damiano Mazza
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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback