TC0

TC⁰ ist ein Komplexitätsklasse benutzt in Komplexität der Schaltung. Es ist die erste Klasse in der Hierarchie von TC Klassen.

TC⁰ enthält alle Sprachen, die von entschieden werden von Boolesche Schaltungen mit konstanter Tiefe und Polynomgröße, die nur unbegrenzter Fan-In enthält Und Tore, Oder Tore, Keine Tore, und Mehrheitstore. Äquivalent können Schwellentore anstelle von Mehrheitsstätten verwendet werden.

TC⁰ enthält mehrere wichtige Probleme wie Sortieren n n-bitnummern, multiplizieren Sie zwei n-bitnummern, ganzzahlige Abteilung^[1] oder das Erkennen der Dyck -Sprache mit zwei Arten von Klammern.

Komplexitätsklassenbeziehungen

Wir können TC erzählen⁰ zu anderen Schaltungsklassen, einschließlich AC⁰ und NC¹; Vollmer 1999 p. 126 Staaten:

$oder }}^{1}.}$

Vollmer stellt fest, dass die Frage, ob die letzte Einbeziehung oben streng ist, "eines der wichtigsten offenen Probleme in der Schaltungskomplexität" ist (ebenda).

Wir haben auch diese Uniform ${\ displaystyle {\ mathsf {tc}}^{0} \ subsetneq {\ mathsf {pp}}}$. (Allender 1996, zitiert in Burtschick 1999).

Grundlage für einheitlich ${\ displayStyle {\ mbox {tc}}^{0}}$

Die funktionale Version der Uniform ${\ displayStyle {\ mbox {tc}}^{0}}$ fällt mit dem Verschluss in Bezug auf die Zusammensetzung der Projektionen und eines der folgenden Funktionssätze zusammen $oder n \ rfloor ^{2}} \}}$, $oder M \ rfloor} \}}$.^[2] Hier ${\ displayStyle n \, {\ stackrel {.} {-}} \, m = \ max (0, n-m)}$, ${\ displayStyle n \ Wedge m}$ ist bitweise und von ${\ displayStyle n}$ und ${\ displayStyle m}$. Mit funktionaler Version bedeutet eins die Menge aller Funktionen ${\ displayStyle f (x_ {1}, \ ldots, x_ {n})}$ über nicht negative Ganzzahlen, die durch Funktionen von begrenzt sind FP und ${\ displayStyle (y {\ text {-th bit von}} f (x_ {1}, \ ldots, x_ {n}))}$ ist in der Uniform ${\ displayStyle {\ mbox {tc}}^{0}}$.

Verweise

• Allender, E. (1996). "Eine Notiz an den unteren Grenzen der gleichmäßigen Schaltung für die Zählhierarchie". Proceedings 2. International Computing and Combinatorics Conference (Cocoon). Springer Vorlesungsnotizen in Informatik. Vol. 1090. S. 127–135.
• Clote, Peter; Kranakis, Evangelos (2002). Boolesche Funktionen und Berechnungsmodelle. Texte in theoretischer Informatik. Eine EATCS -Serie. Berlin: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046.
• Vollmer, Heribert (1999). Einführung in die Komplexität der Schaltung. Ein einheitlicher Ansatz. Texte in theoretischer Informatik. Berlin: Springer-Verlag. ISBN 3-540-64310-9. Zbl 0931.68055.
• Burtschick, Hans-Jörg; Vollmer, Heribert (1999). "Lindström -Quantifizierer und Blattsprachendefinierbarkeit". ECCC TR96-005. {{}}: Journal zitieren erfordert |journal= (Hilfe)

Externe Links

• Komplexitätszoo: TC⁰