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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ this is area of active research. see NTime(n^k) =? DTime(n^k) / cstheory.se $\endgroup$
    – vzn
    Jun 23, 2015 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, 2015 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, 2015 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, 2015 at 16:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.