Alternation-Bounded Semi-unbounded Fan-in Cascading Circuits and the Complementation Closure Property
摘要
Semi-unbounded fan-in circuit families have played an important role in characterizing languages accepted by nondeterministic auxiliary pushdown automata. Such families of polynomial-size circuits of depth \(O(\log ^k{n})\) induce the complexity class \(\textrm{SAC}^k\) . As a natural extension of these circuit families, another model of semi-unbounded fan-in cascading circuits was introduced in 2022 with the use of additional gates, called AND \(_{(\omega )}\) gates, of unbounded fan-out. The nondeterminism-vs-co-nondeterminism question (or the complementation closure property question) has been centering in computational complexity theory. The complementation closure property is still unknown for \(\textrm{NP}\) and \(\textrm{NEXP}\) , whereas \(\textrm{NL}\) and \(\textrm{SAC}^k\) are well-known to be closed under complementation. We particularly focus on the languages accepted by uniform families of polynomial-size semi-unbounded fan-in k-cascading circuits of \(O(\log ^{r}n)\) alternations. We prove that the collection of those languages indeed enjoys the complementation closure property. This result significantly improve the known fact of \(\textrm{SAC}^k=\textrm{co}\text {-}\textrm{SAC}^k\) .