1987 | ReviewPaper | Buchkapitel
The complexity of symmetric boolean functions
verfasst von : Ingo Wegener
Erschienen in: Computation Theory and Logic
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The class of symmetric Boolean functions contains many fundamental functions, among them all types of counting functions. Hence the efficient computation of symmetric functions is a fundamental problem in computer science. Known results on the complexity of symmetric functions in several models of computation are described and new results on the complexity of symmetric functions with respect to bounded depth circuits and parallel random access machines are presented.