# 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? Sep 22, 2010 at 22:39
• Yes. Sorry for the typo. Fixed it now. Sep 23, 2010 at 0:29

## 1 Answer

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.

• Vinay, you can use regular latex in the answer: it might help make it a bit more readable Sep 23, 2010 at 7:06