Direkt zum Inhalt

Lexikon der Mathematik: ACk

die Sprachklasse aller Folgen Boolescher Funktionen fn : {0, 1}n → {0, 1}, die sich in Schaltkreisen mit unbeschränktem fan-in über dem Bausteinsatz AND, OR und NOT (Konjunktion, Disjunktion, NOT-Funktion) mit polynomiell vielen Bausteinen in Tiefe O(logkn) berechnen lassen.

Funktionen in ACk lassen sich mit vertretbarem Aufwand hardwaremäßig realisieren und sind bei Parallelverarbeitung sehr effizient auszuwerten. Für k = 0 genügt konstante Parallelzeit. Die Addition zweier Binärzahlen ist in AC0 enthalten, während die Multiplikation zweier Binärzahlen zwar in AC1 und sogar in NC1, aber nicht in AC0 enthalten ist.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.