Direkt zum Inhalt

Lexikon der Mathematik: TCk

Sprachklasse aller Folgen Boolescher Funktionen \begin{eqnarray}{f}_{n}:{\{0,1\}}^{n}\to \{0,1\},\end{eqnarray}

die sich in Thresholdschaltkreisen mit polynomiell beschränkten Gewichten mit polynomiell vielen Bausteinen in Tiefe O(logk n) berechnen lassen.

Bereits für k = 0, d. h. konstante Tiefe, ergibt sich ein mächtiges Berechnungsmodell. In TC0 sind alle arithmetischen Funktionen enthalten.

Seit langem ist es die größte Herausforderung im Gebiet Komplexität Boolescher Funktionen, für ein Problem in NP zu zeigen, daß die zugehörige Folge Boolescher Funktionen nicht in Thresholdschaltkreisen polynomieller Größe in Tiefe 3 realisierbar ist.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos