3
$\begingroup$

Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with some polynomial bounded running time P(n) on input with length n such that it's not equivalent to any deterministic Turing machine with running time bounded by cP(n)?

If not is there any lower bound known?

--

Sorry for the basic knowledge question but I tried to ask ChatGPT and it lied and said that any non-deterministic Turing machine with running time $n^k$ could be simulated by a deterministic Turing machine running in time $n^{ck}$ until I pointed out that implied a solution to P vs NP.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You can get slightly super-linear bounds if you try to lower bound $T\cdot S$, e.g. the (multiplied) time+space of any algorithm solving an NP-complete problem (generally 3SAT). See here. For time only lower bounds the best I remember seeing is $T\geq cn$ for some explicit $c$ (maybe it was like 5? But this is probably dependent on the computational model). But I'm not a complexity theorist so I'll leave this as a comment. $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 23 at 23:20
  • $\begingroup$ @MarkSchultz-Wu That's very interesting. Are you suggesting that in general my question is equivalent to simply asking for a lower bound for solving 3-SAT since that has a linear time solution on a non-deterministic Turing machine (I think)? I'm not convinced that you couldn't have this fail for some non-linear P even if there was a linear deterministic algorithm for solving SAT but maybe I'm missing something. $\endgroup$
    – Peter Gerdes
    Commented Sep 24 at 2:37
  • 1
    $\begingroup$ The point is that if you want to say ALL NP problems require quadratic (say) time, we would need this to hold for each specific problem at least. 3SAT is probably the best-studied problem, but our lower bounds for this problem are fairly weak. I do not believe the situation is better for other problems, but as I mentioned I’m not a complexity theorist. $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 24 at 6:24

0

Reset to default

You must log in to answer this question.