Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 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)$?

share|improve this question

1 Answer 1

up vote 10 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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