<p>Of course the equalities and inclusions claimed in the question hold only for <em>uniform</em> $\mathsf{NC}^k$. The class $\mathsf{AALTSP}(\log^k n, \log n)$ is the same as uniform $\mathsf{AC}^k$, so the question is the same as whether $\mathsf{NC}^k = \mathsf{AC}^k$.</p>

<p>In particular the case $k=1$ implies that $\mathsf{L}$ is equal to $\mathsf{NL}$ and even $\mathsf{LogCFL}$, since $\mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{LogCFL} \subseteq \mathsf{AC}^1$.  </p>

CC BY-SA 3.0
2013-01-31T08:51:32.747Z
2013-01-31T08:51:32.747Z
Jan Johannsen
<p>Let $\mathsf{ATISP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt in time $f(n)$ using space $g(n)$. Let $\mathsf{AALTSP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt using $f(n)$ alternations and space $g(n)$.</p>

<p>Ruzzo <a href="https://www.sciencedirect.com/science/article/pii/0022000081900386">proved</a> that $\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n)$. He also showed that $\mathsf{NC}^k \subseteq \mathsf{AALTSP}(\log^k n, \log n) \subseteq \mathsf{NC}^{k + 1}$.</p>

<p>Is $\mathsf{NC}^k = \mathsf{AALTSP}(\log^k n, \log n)$?</p>

<cc.complexity-theory><complexity-classes><structural-complexity>
Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?
argentpepper
# Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?

(Asked by: username_0 on 2013-01-30)

Let $\mathsf{ATISP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt in time $f(n)$ using space $g(n)$. Let $\mathsf{AALTSP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt using $f(n)$ alternations and space $g(n)$.

Ruzzo [proved](https://www.sciencedirect.com/science/article/pii/0022000081900386) that $\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n)$. He also showed that $\mathsf{NC}^k \subseteq \mathsf{AALTSP}(\log^k n, \log n) \subseteq \mathsf{NC}^{k + 1}$.

Is $\mathsf{NC}^k = \mathsf{AALTSP}(\log^k n, \log n)$?

**Tags:** cc.complexity-theory, complexity-classes, structural-complexity

---

## 1 answers

### Answer by username_1 on 2013-01-31. Score: 11 | Accepted answer

Of course the equalities and inclusions claimed in the question hold only for *uniform* $\mathsf{NC}^k$. The class $\mathsf{AALTSP}(\log^k n, \log n)$ is the same as uniform $\mathsf{AC}^k$, so the question is the same as whether $\mathsf{NC}^k = \mathsf{AC}^k$.

In particular the case $k=1$ implies that $\mathsf{L}$ is equal to $\mathsf{NL}$ and even $\mathsf{LogCFL}$, since $\mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{LogCFL} \subseteq \mathsf{AC}^1$.


---

