We aim to show that, for a significant class of functions, the representation through EP circuit is more compact than the corresponding Boolean circuit representation.
To this aim we need to introduce the following definitions.
Definition 1 (
Total influence)
The total influence [5] of a Boolean function is the sum
of the individual influences of its variables
Definition 2
For an odd integer , the majority function
equals if and only if
.
Alon-Boppana's theorem [2] affirms that, if a Boolean function is expressed by a
-level circuit composed by the connectives AND-OR with size , then
|
(6) |
where is a suitable constant. Thus, for -levels
circuits the following inequality holds:
|
(7) |
Consequently, since it can be simply verified that
, we
obtain that, for the class of the majority functions
and, then, that the size of a -level circuit
that represents a majority function
increases exponentially with the number of its variables.
On the contrary, a majority function with
entries can be represented by using an
EP circuit with size , independently from . As a matter of fact, for representing it is sufficient to use a single ES composed by all the
variables with
. Thus, we obtain the following expression for
leading to an EP circuit with size .
We can conclude that EP representation is more compact w.r.t. to the
corresponding positive Boolean circuit representation.