TC (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In der Komplexitätstheorie, speziell der Schaltkreiskomplexität, ist TC eine Komplexitätsklasse und TCi eine Hierarchie von Komplexitätsklassen. Für jedes enthält TCi die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe , 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

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 | Quelltext bearbeiten]

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

Daraus folgt NC = AC = TC. Zudem ist

folgt daraus, dass Parity und Majority, die beide in TC0 liegen, nicht in AC0 liegen.[2]

Uniformes ist echt in PP enthalten.[3]

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 die Beziehung gilt.

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

Einzelnachweise

[Bearbeiten | Quelltext 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. 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]).
  • TC. In: Complexity Zoo. (englisch)