Information Technology Reference
In-Depth Information
This theorem establishes that the binary sorting
f
(
n
)
n
has size
O
(
n
2
)
.Infact,
a linear-size circuit can be constructed for it, as stated in Problem
2.17
.
n
sort
:
B
→B
2.12
Most Boolean Functions Are Complex
As we show in this section, the circuit size and depth of most Boolean functions
f
:
n
→B
on
n
variables are at least exponential and linear in
n
, respectively. Furthermore, we show in
Section
2.13
that such functions can be realized with circuits whose size and depth are at most
exponential and linear, respectively, in
n
. Thus, the circuit size and depth of most Boolean
functions on
n
variables are tightly bounded. Unfortunately, this result says nothing about the
size and depth of a specific function, the case of most interest.
Each Boolean function on
n
variables is represented by a table with 2
n
rows and one
column of values for the function. Since each entry in this one column can be completed in
one of two ways, there are 2
2
n
ways to fill in the column. Thus, there are exactly 2
2
n
Boolean
functions on
n
variables. Most of these functions cannot be realized by small circuits because
there just are not enough small circuits.
B
THEOREM
2.12.1
Let
0
<<
1
. The fraction of the Boolean functions
f
:
B
n
→B
that
2
−
(
/
2
)
2
n
when
have size complexity
C
Ω
0
(
f
)
satisfying the following lower bound is at least
1
−
)
/
]log
2
[(
3
e
)
2
(
1
n
≥
2
[(
1
−
−
/
2
)]
.(Here
e
=
2
.
71828
...
isthebaseofthenatural
logarithm.)
2
n
n
(
1
2
n
2
C
Ω
0
(
f
)
≥
−
)
−
Proof
Each circuit contains some number, say
g
, of gates and each gate can be one of the
three types of gate in the standard basis. The circuit with no gates computes the constant
functions with value of 1 or 0 on all inputs.
An input to a gate can either be the output of another gate or one of the
n
input variables.
(Since the basis
Ω
0
is
, no gate need have a constant input.) Since each
gatehasatmosttwoinputs,thereareatmost
(
g
{
AND
,
OR
,
NOT
}
1
+
n
)
2
ways to connect inputs to one
−
gate and
(
g
1
+
n
)
2
g
ways to interconnect
g
gates. In addition, since each gate can be
one of three types, there are 3
g
ways to name the gates. Since there are
g
!
orderings of
g
items (gates) and the ordering of gates does not change the function they compute, at
most
N
(
g
)=
3
g
(
g
+
n
)
2
g
/g
!
distinct functions can be realized with
g
gates. Also, since
g
!
−
g
g
e
−g
≥
(see Problem
2.2
) it follows that
(
3
e
)
g
[(
g
2
+
2
gn
+
n
2
)
/g
]
g
(
3
e
)
g
(
g
+
2
n
2
)
g
N
(
g
)
≤
≤
The last inequality follows because 2
gn
+
n
2
≤
2
gn
2
for
n
≥
2. Since the last bound is an
(
3
e
)
G
increasing function of
g
,
N
(
0
)=
2and
G
+
1
≤
for
G
≥
1, the number
M
(
G
)
of
functions realizable with between 0 and
G
gates satisfies
(
x
x
)
1
/a
(
G
+
1
)(
3
e
)
G
(
G
+
2
n
2
)
G
[(
3
e
)
2
(
G
+
2
n
2
)]
G
M
(
G
)
≤
≤
≤
where
x
=
a
(
G
+
2
n
2
)
and
a
=(
3
e
)
2
. With base-2 logarithms, it is straightforward to
show that
x
x
2
x
0
≤
if
x
≤
x
0
/
log
2
x
0
and
x
0
≥
2.
2
(
1
−δ
)
2
n
for 0
<δ<
1, at most a fraction 2
(
1
−δ
)
2
n
/
2
2
n
=
2
−δ
2
n
of the
If
M
(
G
)
≤
Boolean functions on
n
variables have circuits with
G
or fewer gates.
Search WWH ::
Custom Search