ALCOMFT-TR-02-2

Joan Boyar, Ren\'e Peralta and Denis Pochuev
Concrete Conjunctive Complexity of Symmetric Functions
Århus. Work package 4. January 2002.

Abstract: The conjunctive complexity of a Boolean function f is defined as the minimum number of conjunction (AND) gates required to construct a circuit representing f, when only exclusive-or, conjunction and negation gates may be used. This article explores in detail the conjunctive complexity of symmetric Boolean functions. New techniques that allow such exploration are introduced. Several upper and lower bounds on the conjunctive complexity of symmetric functions are given. In many cases, the upper and lower bounds meet, giving the exact conjunctive complexity of the function.

Postscript file: ALCOMFT-TR-02-2.ps.gz (104 kb).