1
$\begingroup$

For every nondeterministic Turing machine, must there exist an equivalent deterministic one that runs in no more than twice the time?

Why or why not? Can anyone explain?

$\endgroup$

1 Answer 1

1
$\begingroup$

If this were the case, then we would have P${}={}$NP, since then any polynomial-time NTM could be made into a polynomial-time DTM.

Your question is whether NTIME$(f(n))\subseteq{}$DTIME$(2f(n))$ for any function $f\colon\mathbb N\to\mathbb N$. For $f\in\omega(n)$, one has DTIME$(2f(n))={}$DTIME$(f(n))$. So in this case, the question boils down to whether NTIME$(f(n))={}$DTIME$(f(n))$ or not. This question seems open.

What is known is that DTIME$(n)\subsetneq{}$NTIME$(n)$, see https://people.math.gatech.edu/~trotter/papers/34.pdf

It is also known that NTIME$(f(n))\subseteq{}$DTIME$(2^{O(f(n))})$, so you can simulate any NTM by a DTM with exponential slowdown.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.