TC (Komplexitätsklasse)
# 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 $i\in \mathbb {N}$ enthält $TC^i$ die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe $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

    ${\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:

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

Daraus folgt NC = AC = TC. Zudem ist

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

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

Uniformes ${\mbox{TC}}^{0}$ ist echt in PP enthalten.

## 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 $i\in \mathbb {N}$ die Beziehung ${\mbox{TC}}^{i}\subsetneq {\mbox{TC}}^{i+1}$ gilt.

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

