TC (complexity)

In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class of decision problems that can be recognized by threshold circuits, which are Boolean circuits with AND, OR, and Majority gates. For each fixed i, the complexity class TCi consists of all languages that can be recognized by a family of threshold circuits of depth O(login), polynomial size, and unbounded fan-in. The class TC is defined via

TC=⋃i≥0TCi.

## Relation to NC and AC

The relationship between the TC, NC and the AC hierarchy can be summarized as follows:

NCi⊆ACi⊆TCi⊆NCi+1.

In particular, we know that

NC0⊊AC0⊊TC0⊆NC1.

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.[1][2]

As an immediate consequence of the above containments, we have that NC = AC = TC.

## References

1. ↑ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984), "Parity, circuits, and the polynomial-time hierarchy", Mathematical Systems Theory 17 (1): 13–27, doi:10.1007/BF01744431 .
2. ↑ Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio, Randomness and Computation, Advances in Computing Research, 5, JAI Press, pp. 6–20, ISBN 0-89232-896-7, archived from the original on 2012-02-22, https://web.archive.org/web/20120222163102/http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf

* Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.

* v
* t
* e

Important complexity classes (more)

Considered feasible|

* DLOGTIME
* AC0
* ACC0
* TC0
* L
* SL
* RL
* NL
* NC
* SC
* CC
* P
* P-complete
* ZPP
* RP
* BPP
* BQP
* APX

Suspected infeasible|

* UP
* NP
* NP-complete
* NP-hard
* co-NP
* co-NP-complete
* AM
* QMA
* PH
* ⊕P
* PP
* #P
* #P-complete
* IP
* PSPACE
* PSPACE-complete

Considered infeasible|

* EXPTIME
* NEXPTIME
* EXPSPACE
* 2-EXPTIME
* ELEMENTARY
* PR
* R
* RE
* ALL

Class hierarchies|

* Polynomial hierarchy
* Exponential hierarchy
* Grzegorczyk hierarchy
* Arithmetical hierarchy
* Boolean hierarchy

Families of classes|

* DTIME
* NTIME
* DSPACE
* NSPACE
* Probabilistically checkable proof
* Interactive proof system

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/TC (complexity). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=TC_(complexity)&oldid=303707"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template