Direkt zum Inhalt

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(logkn) 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.

  • 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.