# P vs NP and the Time Hierarchy

Assuming $$P\neq NP$$, is it possible that there exists a $$k$$ such that $$P\subseteq\textsf{NTIME}(t^k)$$?

There reason I ask this is that I assume the following: $$P=NP \implies \forall k\ \exists j.\ \textsf{NTIME}(t^k)\subseteq\textsf{DTIME}(t^j)$$ but I know that these statements are not exactly contrapositive to each other.

• this is area of active research. see NTime(n^k) =? DTime(n^k) / cstheory.se
– vzn
Jun 23, 2015 at 15:23
• "for all $j$, $\textsf{DTIME}(t^j)$" could be substituted by P and I think you could add some "$\in\mathbb{N}$". I tried to edit but my edit has been rejected, is this substitution not correct ? Jun 23, 2015 at 18:15
• @FrançoisGodi The substitution is correct but edits should only be made if they actually improve the question. The original text is also correct and your proposed edit was just rephrasing for no particular reason. Indeed, the original seems clearer, since the two statements about the relationship between deterministic and nondeterminstic time are more easily compared as they are written here. Jun 23, 2015 at 22:05
• "I assume" is not needed, what follows is a logical fact: P = NP iff for all $k$ there exists a $j$ such that NTIME($n^k$) is contained in DTIME($n^j$). Aug 14, 2015 at 16:17