TC0

From Wikipedia, the free encyclopedia

TC⁰ is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.

TC⁰ 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.

TC⁰ contains several important problems, such as sorting n n-bit numbers, and multiplying two n-bit numbers, integer division,^[1] recognizing the Dyck language with two types of parentheses.

Complexity class relations

We can relate TC⁰ to other circuit classes, including AC⁰ and NC¹; Vollmer 1999 p. 126 states:

${\mbox{AC}}^{0}\subsetneq {\mbox{AC}}^{0}[p]\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}.$

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 ${\mbox{TC}}^{0}\subsetneq {\mbox{PP}}$ . (Allender 1996, as cited in Burtschick 1999).

References

↑ Hesse, William; Allender, Eric; Mix Barrington, David (2002). "Uniform constant-depth threshold circuits for division and iterated multiplication". Journal of Computer and System Sciences 65: 695–716. doi:10.1016/S0022-0000(02)00025-9.

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.

External links

Complexity Zoo: TC⁰

v t e Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP

Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.