I apologize if this is a silly question, but could someone tell me whether the class polyL (polylogarithmic space) is equal to the class ATIME(polylog)? If so, where can I find a reference to this or is it obvious?


closed as off-topic by Raphael, Jan Johannsen, Emil Jeřábek, Kaveh, Yuval Filmus Sep 25 '17 at 13:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Raphael, Jan Johannsen, Emil Jeřábek, Kaveh, Yuval Filmus
If this question can be reworded to fit the rules in the help center, please edit the question.


$SPACE[polylog(n)]=ATIME[polylog(n)]$ citing that $ATIME[s(n)]\subseteq SPACE[s(n)]\subseteq ATIME[(s(n))^2]$. This follows from a modified proof of Savitch's Theorem and is a pretty standard exercise in Complexity Theory courses. I'm not sure where this theorem first appeared, but I'll happily add a link to the paper if I find it or if someone links it in the comments.

  • $\begingroup$ And these inclusions hold for sublinear bounds as well? $\endgroup$ – springer77 Sep 22 '17 at 3:03
  • $\begingroup$ It does require random access (so it will not hold for strict Turing machines). $\endgroup$ – Dylan McKay Sep 22 '17 at 3:22
  • 3
    $\begingroup$ It’s difficult to pinpoint a single original reference for these results, as they are in a sense older than the “random access” Turing machine model itself. Anyway, the following papers in between them should cover all the relevant material: Borodin, On relating time and space to size and depth; Chandra, Kozen, Stockmayer, Alternation; Ruzzo, On uniform circuit complexity. $\endgroup$ – Emil Jeřábek Sep 22 '17 at 11:51

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