Information Technology Reference
In-Depth Information
THEOREM
9.4.1
For every complete basis
Ω
there is a constant
c
Ω
such that for every function
f
(
n
)
and every partition of its variables
X
into disjoint sets
X
1
,
X
2
,
...
,
X
p
,the
formula size of
f
with respect to
Ω
satisfies the following lower bound:
:
B
n
→B
p
L
Ω
(
f
)
≥
c
Ω
log
2
r
X
j
(
f
)
j
=
1
Proof
Consider
T
, a minimal circuit of fan-out 1 for
f
.Let
n
j
be the number of instances
of variables in
X
j
that are labels for leaves in
T
.Thenbydefinition
L
Ω
(
f
)=
i
=
1
n
j
.
Let
d
be the fan-in of the basis
Ω
.
For each
j
,1
p
, we define the subtree
T
j
of
T
consisting of paths from vertices
with labels in
X
j
to the output vertex, as suggested by the heavy lines in Fig.
9.6
.We
observe that some vertices in such a subtree have one input from a vertex in the subtree
T
j
(called
controllers
— shaded vertices in Fig.
9.6
) whereas others have more than one input
from a vertex in
T
j
(
combiners
— black vertices in Fig.
9.6
). Each type of vertex typically
has inputs from vertices other than those in
T
j
, that is, from vertices on paths from input
vertices in
X
≤
j
≤
X
j
.
When the variables
X
−
X
j
are assigned values, the output of a controller or com-
biner vertex depends only on the inputs it receives from other vertices in
T
j
.Thefunction
computed by a controller is a function of its one input
y
in
T
j
and can be represented as
(
a
−
b
for some values of the constants
a
and
b
. These constants are determined by
the values of inputs in
X
∧
y
)
⊕
X
j
. We assume without loss of generality that each chain of
controllers with no intervening combiners is compressed to one controller. The combiner is
also some function of its inputs from other vertices in
T
j
. Since the number of such inputs
is as least 2, a combiner (with fan-in at most
d
) has at most
d
−
−
2 inputs determined by
variables in
X
−
X
j
.
Combiner
Controller
x
5
x
4
x
3
x
1
x
2
x
7
x
1
x
2
x
7
x
4
x
3
x
2
x
5
Figure 9.6
The subtree
T
j
of the tree
T
is identified by heavy edges on paths from input vertices
in the set
X
j
.Verticesin
T
j
that have one heavy input edge are controller vertices.
Other vertices in
T
j
are combiner vertices.
=
{
x
1
,
x
3
}
Search WWH ::
Custom Search