TC (complexity)
Encyclopedia
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 circuit
s with depth
and a polynomial number
of unlimited-fanin AND
, OR gate
s and Majority gates. The class TC is defined as
and the AC
hierarchy can be summarized as
In particular, we know that
The first strict containment follows from the fact that NC0 cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC0 and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC0 ⊊ TC0 follows because parity and majority (which are both in TC0) were shown to be not in AC0.
As an immediate consequence of the above containments, we have that NC = AC = TC.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, and specifically computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and 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....
, 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:...
, and TCi is a hierarchy of complexity classes. Each class TCi consists of the languages
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
recognized 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 depth
and a polynomial numberPolynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
of unlimited-fanin AND
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...
, 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. The class TC is defined as
Relation to NC and AC
The relationship between the TC, NCNC (complexity)
In complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O using O parallel processors...
and the AC
AC (complexity)
In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth O and a polynomial number of unlimited-fanin AND and OR gates....
hierarchy can be summarized as
In particular, we know that
The first strict containment follows from the fact that NC0 cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC0 and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC0 ⊊ TC0 follows because parity and majority (which are both in TC0) were shown to be not in AC0.
As an immediate consequence of the above containments, we have that NC = AC = TC.