$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$ ?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Are $k$ and $i$ meant to be the same thing? $\endgroup$– András SalamonCommented Sep 22, 2010 at 22:39
-
$\begingroup$ Yes. Sorry for the typo. Fixed it now. $\endgroup$– Shiva KintaliCommented Sep 23, 2010 at 0:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Vinay, you can use regular latex in the answer: it might help make it a bit more readable $\endgroup$ Commented Sep 23, 2010 at 7:06