In their paper "Alternation" Chandra et al. show how an Alternating Turing Machine can simulate a Deterministic Turing Machine with time-complexity $t(n)$ using only $\log(t(n))$ space what implies $P \subseteq AL$.

I wonder why one cannot use the same (or at least a quite similar) construction in order to simulate a Non-deterministic Turing machine with time complexity $t(n)$ using only $\log(t(n))$ space.

  • $\begingroup$ Possibly, a word "monotone" influences. $\endgroup$ – rus9384 Sep 29 '17 at 1:19
  • $\begingroup$ Have you read the paper? The proof requires $\log t(n)$ alternations. Only one alternation won't do. $\endgroup$ – Yuval Filmus Sep 29 '17 at 6:44

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.