TC (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 circuits with depth and a polynomial number of unlimited-fanin AND, OR gates and Majority gates. The class TC is defined as

Relation to NC and AC[edit]

The relationship between the TC, NC 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 AC0TC0 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[edit]

  1. ^ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
  2. ^ 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.