TC0 contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded-fanin AND gates, OR gates, and majority gates. Equivalently, threshold gates can be used instead of majority gates.
Complexity class relations
Vollmer states that the question of whether the last inclusion above is strict is "one of the main open problems in circuit complexity" (ibid.).
We also have that uniform . (Allender 1996, as cited in Burtschick 1999).
- Allender, E. (1996). "A note on uniform circuit lower bounds for the counting hierarchy". Proceedings 2nd International Computing and Combinatorics Conference (COCOON). Springer Lecture Notes in Computer Science 1090. pp. 127–135.
- Clote, Peter; Kranakis, Evangelos (2002). Boolean functions and computation models. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046.
- Vollmer, Heribert (1999). Introduction to Circuit Complexity. A uniform approach. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. ISBN 3-540-64310-9. Zbl 0931.68055.
- Burtschick, Hans-Jörg; Vollmer, Heribert (1999). Lindström Quantifiers and Leaf Language Definability. ECCC TR96-005.