<p>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 </p>

<p>$$\mathsf{SAC^k} = \mathsf{NAuxPDA}(\log n, \log^k n);$$</p>

<p>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: <a href="http://linkinghub.elsevier.com/retrieve/pii/0022000080900367">W. Ruzzo, Tree-size bounded alternation. JCSS 1980.</a></p>

CC BY-SA 2.5
2010-09-23T07:06:22.580Z
Vinay, you can use regular latex in the answer: it might help make it a bit more readable
Suresh Venkat
CC BY-SA 3.0
2010-09-23T06:58:39.207Z
2014-01-17T21:22:00.030Z
2014-01-17T21:22:00.030Z
V Vinay
<p>$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 <a href="http://en.wikipedia.org/wiki/LOGCFL">LogCFL</a> 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$ ?</p>

CC BY-SA 2.5
2010-09-22T22:39:34.933Z
Are $k$ and $i$ meant to be the same thing?
András Salamon
CC BY-SA 2.5
2010-09-23T00:29:51.810Z
Yes. Sorry for the typo. Fixed it now.
Shiva Kintali
<cc.complexity-theory><circuit-complexity><space-bounded><arithmetic-circuits>
Machine characterization of $SAC^i$
Shiva Kintali
# Machine characterization of $SAC^i$

(Asked by: username_0 on 2010-09-22)

$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](http://en.wikipedia.org/wiki/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$ ?

**Tags:** cc.complexity-theory, circuit-complexity, space-bounded, arithmetic-circuits

> **Comments:**
> **username_1**: Are $k$ and $i$ meant to be the same thing?  
> **username_0**: Yes. Sorry for the typo. Fixed it now.  

---

## 1 answers

### Answer by username_2 on 2010-09-23. Score: 14 | Accepted 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.](http://linkinghub.elsevier.com/retrieve/pii/0022000080900367)

> **Comments:**
> **username_3**: Vinay, you can use regular latex in the answer: it might help make it a bit more readable  

---

