TC (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Komplexitätstheorie, speziell der Schaltkreiskomplexität, ist TC eine Komplexitätsklasse und TCi eine Hierarchie von Komplexitätsklassen. Für jedes i \in \N enthält TCi 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 ACi, 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[Bearbeiten]

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

\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 TC0 liegen, nicht in AC0 liegen.[2]

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

Hierarchie[Bearbeiten]

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

Differenziert man TC0 nach der Tiefe der Schaltkreise, erhält man Klassen der Form TC^0_i für Probleme, die von TC-Schaltkreisen in Tiefe i gelöst werden können. Es ist bekannt, dass TC^0_1 \subsetneq TC^0_2 \subsetneq TC^0_3 gilt.[4]

Einzelnachweise[Bearbeiten]

  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. 17, 1984 (http://www.springerlink.com/content/n38782mx4039q322/).
  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. 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. 46, 1993, S. 129-154 (http://www.igi.tugraz.at/psfiles/47.pdf).

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

TC. In: Complexity Zoo. (englisch)