Hierarchies of circuit classes that are closed under complement

Abstract

We examine three hierarchies of circuit classes and show they are closed under complementation. (1) The class of languages recognized by a family of polynomial size skew circuits with width O(w), are closed under complement. (2) The class of languages recognized by family of polynomial size circuits with width O(w) and polynomial tree-size, are closed under complement. (3) The class of languages recognized by a family of polynomial size, O(log(n)) depth, bounded AND fan-in with OR fan-in f (f/spl ges/log(n)) circuits are closed under complement. These improve upon the results of (i) Immerman (1988) and Szelepcsenyi (1988), who show that /spl Nscr//spl Lscr//spl Oscr//spl Gscr/ is closed under complementation, and (ii) Borodin et al. (1989), who show that /spl Lscr//spl Oscr//spl Gscr//spl Cscr//spl Fscr//spl Lscr/ is closed under complement.