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(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!

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

Partnerinhalte

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