Information Technology Reference
In-Depth Information
In this section we show that every bounded-depth circuit for the parity function
f
(
n
)
⊕
over
the basis containing the
NOT
gate on one input and the
AND
and
OR
gates on an arbitrary
number of inputs has exponential size. Thus, the depth-2 result extends to arbitrary depth.
BOUNDED-DEPTH PARITY CIRCUITS HAVE EXPONENTIAL SIZE
We use an approximation method
to derive a lower bound on the size of a bounded-depth circuit for
f
(
n
)
⊕
. This method parallels
almost exactly the method of Section
9.6.3
. Starting with gates most distant from the output
and progressing toward it, replace each gate of a given circuit by an approximating circuit.
We show that as each replacement is made, the number of new errors it introduces is small.
However, we also show that after all gates are approximated, the number of errors between the
approximating circuit and
f
(
n
)
⊕
is large. This implies that the number of gates replaced is large.
The approximation method used here replaces each gate in a circuit by a polynomial over
GF
(
3
)
, the three-element field containing
{−
}
1, 0, 1
, with the property that if the variables
B
=
{
}
B
of such a polynomial assume values in
0, 1
, the value of the polynomial is in
.For
example, the polynomial
x
1
(
1
only when
x
1
=
x
3
=
1and
x
2
=
0 and has value 0 otherwise. Thus, it corresponds exactly to the minterm
x
1
x
2
x
3
.Since
every minterm can be represented as a polynomial of this kind, every Boolean function
f
can
realized by a polynomial over
GF
(
3
)
by forming the sum of one such polynomial for each
of its minterms. A
b
-approximator
is polynomial of degree
b
that approximates a Boolean
function.
Although we establish the lower bound for the basis containing
NOT
and the unbounded
fan-in
AND
and
OR
gates, the result continues to hold if the unbounded fan-in
MOD
3
function
is added to the basis. (See Problem
9.41
.) We begin by showing that the function computed
by a circuit
C
containing
size
(
C
)
gates cannot differ from its
b
-approximator on too many
input tuples.
−
x
2
)
x
3
has value 1 over
B
LEMMA
9.7.6
Let
f
:
B
be computed by a circuit
C
of depth
d
.The e sa
(
2
k
)
d
-
approximator circuit
C
computing
f
:
n
→B
such that
f
and
f
differ on at most
size
(
C
)
2
n−k
input
n
-tuples, where
n
is the number of inputs on which
C
depends and
size
(
C
)
is the number
of gates that it contains.
P
roof
We cons t ruc t a
b
-approximator for
C
,
b
=(
2
k
)
d
, by approximating inputs (
x
i
and
x
i
are approximated exactly on
n
B
→B
x
i
)
), after which we approximate gates all
of whose inputs have been approximated until the output gate has been approximated. We
establish the result of the lemma by induction.
We treat the statement of the lemma as our inductive hypothesis and show that if it holds
for
d
=
D
B
by
x
i
and
(
1
−
1, it holds for
d
=
D
. The hypothesis holds on inputs, namely, when
d
=
0.
Suppose the hypothesis holds for
d
=
D
−
−
1. Since
C
has depth
d
,eachoftheinputstothe
output gate has depth at most
D
1 and satisfies the hypothesis. The output gate is
AND
,
OR
,or
NOT
. Suppose it is
NOT
.Let
g
be the function associated with its input. We replace
the
NOT
gate with the function
(
1
−
−
g
)
, which introduces no new errors. Since
g
and 1
−
g
have the same degree, the inductive hypothesis holds in this case.
If the output gate is the
AND
of
g
1
,
g
2
,
...
,
g
m
, it can be represented exactly by the
function
g
1
g
2
g
m
. However, this polynomial has degree
m
(
2
k
)
d−
1
if each of its inputs
has degree at most
(
2
k
)
d−
1
; this violates the inductive hypothesis if
m>
2
k
,whichmay
happen because the fan-in of the gate is potentially unbounded. Thus we must introduce
some error in order to reduce the degree of the approximating polynomial. Since the
OR
of
···
Search WWH ::
Custom Search