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
$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.