Lexikon der Mathematik: ACCk
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 (Konjunktion) und aller Modulo-Funktionen mit polynomiell vielen Bausteinen in Tiefe O(logk n) berechnen lassen.
Die mod(q)-Funktion liefert die Ausgabe 1 genau dann, wenn die Anzahl der eingehenden Einsen ein Vielfaches von q ist. Die Negation der mod(2)-Funktion ist die PARITY-Funktion. Die Klasse ACCk ist eine Obermenge von ACk.
Funktionen mit polynomiell großer Ring-Summen-Expansion sind in ACC0, aber nicht unbedingt in AC0 enthalten. Es ist ein offenes Problem, für Funktionen in NP nachzuweisen, daß sie nicht in ACC0 enthalten sind.
Schreiben Sie uns!