TC⁰ is a complexity class

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

 used in circuit complexity

Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....

. It is the first class in the hierarchy of TC

TC (complexity)

In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class, and TCi is a hierarchy of complexity classes. Each class TCi consists of the languages recognized by Boolean circuits with depth O and a polynomial number of...

 classes.

TC⁰ contains all languages which are decided by Boolean circuit

Boolean circuit

A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...

s with constant depth and polynomial size, containing only unbounded-fanin AND gate

AND gate

The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output results only if both the inputs to the AND gate are HIGH . If neither or only one input to the AND gate is HIGH, a LOW output results...

s, OR gate

OR gate

The OR gate is a digital logic gate that implements logical disjunction - it behaves according to the truth table to the right. A HIGH output results if one or both the inputs to the gate are HIGH . If neither input is HIGH, a LOW output results...

s, 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.

Complexity class relations

We can relate TC⁰ to other circuit classes, including AC⁰

AC0

AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O and polynomial size, with unlimited-fanin AND gates and OR gates....

 and NC¹; Vollmer 1999 p. 126 states:

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).