TC (Komplexitätsklasse)

In der Komplexitätstheorie, speziell der Schaltkreiskomplexität, ist TC eine Komplexitätsklasse und TC^i eine Hierarchie von Komplexitätsklassen. Für jedes ${\displaystyle i\in \mathbb {N} }$ enthält TC^i die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe ${\displaystyle O(\log ^{i}n)}$, polynomieller Größe, und Und-, Oder-, und Majority-Gattern mit unbeschränktem Fan-In erkannt werden. Die Definition erweitert damit die Klassen AC^i, die keine Majority-Gatter erlaubt. Die Klasse TC ist dann definiert als

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

Ein Majority-Gatter ist dabei ein Gatter, das genau dann 1 ausgibt, wenn mehr als die Hälfte der Eingänge den Wert 1 haben.

Bezug zu anderen Klassen

Zwischen den TC-, NC- und AC-Hierarchien besteht folgende Beziehung:[1]

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

Daraus folgt NC = AC = TC. Zudem ist

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

${\displaystyle {\mbox{AC}}^{0}\subsetneq {\mbox{TC}}^{0}}$ folgt daraus, dass Parity und Majority, die beide in TC^0 liegen, nicht in AC^0 liegen.[2]

Uniformes ${\displaystyle {\mbox{TC}}^{0}}$ ist echt in PP enthalten.[3]

Hierarchie

Wie bei NC und AC und anderen Hierarchien in der Komplexitätstheorie ist unbekannt, ob die TC-Hierarchie echt ist, also ob für alle ${\displaystyle i\in \mathbb {N} }$ die Beziehung ${\displaystyle {\mbox{TC}}^{i}\subsetneq {\mbox{TC}}^{i+1}}$ gilt.

Differenziert man TC^0 nach der Tiefe der Schaltkreise, erhält man Klassen der Form ${\displaystyle TC_{i}^{0}}$ für Probleme, die von TC-Schaltkreisen in Tiefe ${\displaystyle i}$ gelöst werden können. Es ist bekannt, dass ${\displaystyle TC_{1}^{0}\subsetneq TC_{2}^{0}\subsetneq TC_{3}^{0}}$ gilt.[4]

Einzelnachweise

1. Vollmer 1999, Seite 126
2. M. Furst, J. B. Saxe und M. Sipser: Parity, circuits, and the polynomial-time hierarchy. In: Mathematical Systems Theory. Band 17, 1984, S. 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). Band 1090, 1996, S. 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. Band 46, 1993, S. 129–154 (tugraz.at [PDF]). 

Literatur

• 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. 

Weblinks

• TC. In: Complexity Zoo. (englisch)