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

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

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

of decision problems 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 input ...

s with

AND or AND may refer to: Logic, grammar, and computing * Conjunction (grammar), connecting two words, phrases, or clauses * Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition * Bitwise AND, a boolea ...

, OR, and

Majority gate In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of th ...

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

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

. 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