14
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Vinay, you can use regular latex in the answer: it might help make it a bit more readable $\endgroup$ – Suresh Venkat Sep 23 '10 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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