# Machine characterization of $SAC^i$

$SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It is known that $SAC^i$ for $i \geq 1$ is closed under complement and $SAC^0$ is not. Also, $SAC^1 = LogCFL$ and hence has a machine characterization, since LogCFL is the set of languages accepted by an $O({\log}n)$ space bounded and polynomial time bounded auxiliary PDA. Are there similar machine characterizations of $SAC^i$ for $i \geq 2$ ?

• Are $k$ and $i$ meant to be the same thing? – András Salamon Sep 22 '10 at 22:39
• Yes. Sorry for the typo. Fixed it now. – Shiva Kintali Sep 23 '10 at 0:29

Yes. Stack heights. $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$, that is, with $O(\log n)$ space and $O(\log n)$ stack height; this implies $\log n$ configurations and therefore $\log^2(n)$ bits. We have
$$\mathsf{SAC^k} = \mathsf{NAuxPDA}(\log n, \log^k n);$$
these machines will run in time $2^{\log^{k}(n)}$. Without restriction on stack height, we will get exactly $\mathsf{P}$. The result should follow from: W. Ruzzo, Tree-size bounded alternation. JCSS 1980.