In
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
i consists of all languages that can be recognized by a family of threshold circuits of depth
,
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
:
Relation to NC and AC
The relationship between the TC,
NC and the
AC hierarchy can be summarized as follows:
:
In particular, we know that
:
The first strict containment follows from the fact that NC
0 cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC
0 and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC
0 ⊊ TC
0 follows because parity and majority (which are both in TC
0) were shown to be not in AC
0.
As an immediate consequence of the above containments, we have that NC = AC = TC.
References
*
{{ComplexityClasses
Circuit complexity
Complexity classes