9
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ this is area of active research. see NTime(n^k) =? DTime(n^k) / cstheory.se $\endgroup$ – vzn Jun 23 '15 at 15:23
  • $\begingroup$ "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 ? $\endgroup$ – François Jun 23 '15 at 18:15
  • $\begingroup$ @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. $\endgroup$ – David Richerby Jun 23 '15 at 22:05
  • 1
    $\begingroup$ "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$). $\endgroup$ – András Salamon Aug 14 '15 at 16:17

Your Answer

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

Browse other questions tagged or ask your own question.