TC (complexity)

In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class, and TCⁱ is a hierarchy of complexity classes. Each class TCⁱ consists of the languages recognized by Boolean circuits with depth $O(\log^i n)$ and a polynomial number of unlimited-fanin AND, OR gates and Majority gates. The class TC is defined as

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

Relation to NC and AC

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

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

In particular, we know that

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

The first strict containment follows from the fact that NC⁰ cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC⁰ and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC⁰ ⊊ TC⁰ follows because parity and majority (which are both in TC⁰) were shown to be not in AC⁰.^[1]^[2]

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

References

↑ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
↑ Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio, Randomness and Computation (PDF), Advances in Computing Research, 5, JAI Press, pp. 6–20, ISBN 0-89232-896-7

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

Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ 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 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

This article is issued from Wikipedia - version of the 9/8/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.