TC (complexity)

In complexity theory, specifically the circuit complexity, TC is a complex class and TCi is a hierarchy of Komplexitäsklassen. For each TCi contains the formal languages ​​that are recognized by circuit families with depth, polynomial size, and AND, OR, and Majority gates with unbounded fan-in. The definition expands the classes ACi that does not allow Majority gate. Class TC is then defined as

A Majority gate is a gate which outputs 1 if and only if more than half of the inputs have the value 1.

Relation to other classes

The following relationship exists between the TC, NC and AC hierarchies:

It follows NC = AC = TC. In addition,

It follows that Parity and Majority, both located in TC0, not in AC0.

Uniform is properly contained in PP.

Hierarchy

As with NC and AC and other hierarchies in complexity theory is unknown whether the TC hierarchy is genuine, that is, whether the relationship is valid for all.

Differentiating TC0 on the depth of circuits, one obtains classes of the form for problems that can be solved by TC circuits in depth. It is known that the following applies.