TC (Komplexitätsklasse)

In der Komplexitätstheorie, speziell der Schaltkreiskomplexität, ist TC eine Komplexitätsklasse und TCⁱ eine Hierarchie von Komplexitätsklassen. Für jedes $i\in \mathbb{N}$ enthält TCⁱ 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ⁱ, die keine Majority-Gatter erlaubt. Die Klasse TC ist dann definiert als

$\text{TC}=\bigcup _{i\ge 0}{\text{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:

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

Daraus folgt NC = AC = TC. Zudem ist

${\text{NC}}^0⊊{\text{AC}}^0⊊{\text{TC}}^0\subseteq {\text{NC}}^1$

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

Uniformes ${\text{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 ${\text{TC}}^i⊊{\text{TC}}^{i+1}$ gilt.

Differenziert man TC⁰ nach der Tiefe der Schaltkreise, erhält man Klassen der Form $T{C}_i^0$ für Probleme, die von TC-Schaltkreisen in Tiefe $i$ gelöst werden können. Es ist bekannt, dass $T{C}_1^0⊊T{C}_2^0⊊T{C}_3^0$ gilt.

Literatur

• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Vorlage:Complexity Zoo