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 Zwischen den TC-, NC- und AC-Hierarchien besteht folgende Beziehung:Vollmer 1999, Seite 126
Daraus folgt NC = AC = TC. Zudem ist
folgt daraus, dass Parity und Majority, die beide in TC0 liegen, nicht in AC0 liegen.
Uniformes 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 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.
Einzelnachweise
Literatur
Weblinks
Kategorie:Komplexitätsklasse