theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, and specifically

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

and

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 the Boolean circuits that compute them. A related notion is the ci ...

, TC is a

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms ...

decision problems In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

that can be recognized by threshold circuits, which are

Boolean circuit In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible in ...

s with AND, OR, and Majority gates. For each fixed ''i'', the complexity class TCⁱ consists of all languages that can be recognized by a family of threshold circuits of depth

O(\log^i n)

polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...

size, and unbounded

fan-in Fan-in is the number of inputs a logic gate can handle. For instance the fan-in for the AND gate shown in the figure is 3. Physical logic gates with a large fan-in tend to be slower than those with a small fan-in. This is because the complexity ...

. The class TC is defined via :

\mbox = \bigcup_ \mbox^i.

Relation to NC and AC

The relationship between the TC, NC and the AC hierarchy can be summarized as follows: :

\mbox^i \subseteq \mbox^i \subseteq \mbox^i \subseteq \mbox^.

In particular, we know that :

\mbox^0 \subsetneq \mbox^0 \subsetneq \mbox^0 \subseteq \mbox^.

The first strict containment follows from the fact that NC⁰ cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC⁰ and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC⁰ ⊊ TC⁰ follows because parity and majority (which are both in TC⁰) were shown to be not in AC⁰. As an immediate consequence of the above containments, we have that NC = AC = TC.

References

* {{ComplexityClasses Circuit complexity Complexity classes