Information Technology Reference
In-Depth Information
f
v
)
in a very syntactic manner starting from the leaf nodes. Let us make precise this
syntactic computation that we have in mind.
v
R
(
This means that for any node
in a monote circuit over
one can determineMon
Definition 14
(
Formal Monomials
)Let
ʲ
be an arithmetic circuit. The
formal mono-
mials
at any node
v
∗
ʲ
, which shall be denoted by FM
(v)
, shall be inductively
defined as follows:
If
v
is a leaf labelled by a variable
x
i
,thenFM
(v)
=
{
x
i
}
. If it is labelled by a constant, then
FM
(v)
= {
1
}
.
If
v
=
v
1
+
v
2
,thenFM
(v)
=
(v
1
)
∃
(v
2
)
FM
FM
.
If
v
=
v
1
×
v
2
,then
FM
(v)
=
FM
(v
1
)
·
FM
(v
2
)
def
= {
m
1
·
m
2
:
m
1
∗
FM
(v
1
),
m
2
∗
FM
(v
2
)
}
.
Note that for any node
v
in any circuit we have Mon
(
f
v
)
∧
FM
(v)
but in a monotone
circuit over
this containment is in fact an equality at every node. This motivates
our definition of a slightly more general notion of a monotone circuit as follows:
R
Definition 15
(
Monotone circuits
) A circuit
C
is said to be
syntactically monotone
(simply monotone for short) if Mon
(
f
v
)
=
FM
(v)
for every node
v
in
C
.
The main theorem of this section is the following:
Theorem 16
[
JS82
]
Over any field
, any syntactically monotone circuit C com-
puting
Det
n
or
Perm
n
must have size at least
2
ˇ(
n
)
.
F
The proof of this theorem is relatively short assuming the following structural
result (which is present in standard depth-reduction proofs [
VSBR83
,
AJMV98
]).
Lemma 17
Let f be a degree d polynomial computed by a monotone circuit of size
s. Then, f can be written of the form f
=
⊟
i
=
1
f
i
·
g
i
where the f
i
's and
g
i
's satisfy
the following properties:
d
3
2
d
∗[
]
<
deg
g
i
≥
1.
For each i
s
, we have
3
.
(
f
i
)
·
(g
i
)
∧
(
)
2.
For each i , we have
FM
FM
FM
f
.
We shall defer this lemma to the end of the section and first see how this would
imply Theorem 16. The complexity measure
in this case is just the number of
monomials in
f
, but it is the above
normal form
that is crucial in the lower bound.
(
f
)
Proof of Theorem 16
Suppose
ʲ
is a circuit of size
s
that computes
Det
n
. Then by
Lemma 17,
s
⊨
Det
n
=
f
i
·
g
i
i
=
1
