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

CC BY-SA 3.0
2017-09-22T03:03:47.273Z
And these inclusions hold for sublinear bounds as well?
springer77
CC BY-SA 3.0
2017-09-22T03:22:05.123Z
It does require random access (so it will not hold for strict Turing machines).
Dylan McKay
CC BY-SA 3.0
2017-09-22T11:51:19.543Z
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](https://doi.org/10.1137/0206054); Chandra, Kozen, Stockmayer, [Alternation](https://doi.org/10.1145/322234.322243); Ruzzo, [On uniform circuit complexity](https://doi.org/10.1016/0022-0000(81)90038-6).
Emil Jeřábek
CC BY-SA 3.0
2017-09-22T01:40:19.833Z
2017-09-22T01:40:19.833Z
Dylan McKay
<p>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?</p>

<time-complexity><alternation>
polylogarithmic space
springer77
# polylogarithmic space

(Asked by: username_0 on 2017-09-21)

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?

**Tags:** time-complexity, alternation

---

## 1 answers

### Answer by username_1 on 2017-09-22. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: And these inclusions hold for sublinear bounds as well?  
> **username_1**: It does require random access (so it will not hold for strict Turing machines).  
> **username_2**: 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](https://doi.org/10.1137/0206054); Chandra, Kozen, Stockmayer, [Alternation](https://doi.org/10.1145/322234.322243); Ruzzo, [On uniform circuit complexity](https://doi.org/10.1016/0022-0000(81)90038-6).  

---

