3
$\begingroup$

It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a deterministic UTM can simulate another deterministic TM with running time $t(n)$ in time $ t(n)\log(t(n))$.

My question is: why is there a $\log(t(n))$ slowdown in the simulation of a deterministic TM by a UTM, as opposed to a constant factor slowdown in the nondeterministic case?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Have you tried looking at the proofs of these simulations? If what you're stating is correct, then some trick that works for nondeterministic machines doesn't work for deterministic ones. $\endgroup$
    – Yuval Filmus
    Commented Feb 23, 2014 at 19:10

1 Answer 1

Reset to default
1
$\begingroup$

Please refer to the answer in the similar question, "Why is simulation by non deterministic Turing machine faster than a deterministic one?".

Basically, in the non-deterministic universal Turing machine we guess the contents of the tape and check if the guess is correct later on. This allows us to save time going to and fro in the work tape.

Improve this answer
$\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.