TC (complexity class)

In complexity theory , specifically the circuit complexity , is TC a complexity class and TC ⁱ a hierarchy of classes complexity. For each contains TC ⁱ the formal languages that of circuit families with depth , polynomial size, and And- , Oder , and Majority gates with unlimited fan-in to be recognized. The definition thus extends the AC ⁱ classes , which do not allow majority gates. The class TC is then defined as ${\displaystyle i\in \mathbb {N} }$ ${\displaystyle O(\log ^{i}n)}$

${\displaystyle {\mbox{TC}}=\bigcup _{i\geq 0}{\mbox{TC}}^{i}.}$

A majority gate is a gate that outputs 1 exactly when 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:

${\displaystyle {\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{TC}}^{i}\subseteq {\mbox{NC}}^{i+1}.}$

From this it follows NC = AC = TC. In addition, is

${\displaystyle {\mbox{NC}}^{0}\subsetneq {\mbox{AC}}^{0}\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}}$

${\displaystyle {\mbox{AC}}^{0}\subsetneq {\mbox{TC}}^{0}}$it follows from this that parity and majority, which are both in TC ^0, are not in AC ⁰ .

Uniforms are really contained in PP . ${\displaystyle {\mbox{TC}}^{0}}$

hierarchy

As with NC and AC and other hierarchies in complexity theory, it is unknown whether the TC hierarchy is real, i.e. whether the relationship applies to all . ${\displaystyle i\in \mathbb {N} }$ ${\displaystyle {\mbox{TC}}^{i}\subsetneq {\mbox{TC}}^{i+1}}$

If one differentiates TC ⁰ according to the depth of the circuits, one obtains classes of the form for problems that can be solved in depth by TC circuits . It is known that . ${\displaystyle TC_{i}^{0}}$ ${\displaystyle i}$ ${\displaystyle TC_{1}^{0}\subsetneq TC_{2}^{0}\subsetneq TC_{3}^{0}}$

Individual evidence

1. ↑ Vollmer 1999, page 126
2. ^ M. Furst, JB Saxe and M. Sipser: Parity, circuits, and the polynomial-time hierarchy . In: Mathematical Systems Theory . tape 17 , 1984, pp. 13-27 , doi : 10.1007 / BF01744431 .
3. ^ E. Allender: A note on uniform circuit lower bounds for the counting hierarchy . In: Proceedings 2nd International Computing and Combinatorics Conference (COCOON) (=  Springer Lecture Notes in Computer Science ). tape 1090 , 1996, pp. 127-135 .
4. ^ András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán: Threshold Circuits of Bounded Depth . In: Journal of Computer and System Sciences . tape 46 , 1993, pp. 129–154 ( tugraz.at [PDF]).

literature

• Stasys Jukna: Boolean function complexity. Advances and frontiers . Springer, 2012, ISBN 978-3-642-24507-7 .
• Heribert Vollmer : Introduction to Circuit Complexity: a Uniform Approach . Springer , 1999, ISBN 3-540-64310-9 .

Web links

• TC . In: Complexity Zoo. (English)