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.
Copyright Springer Verlag GmbH Deutschland 2017
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.