Information Technology Reference
In-Depth Information
∗
[
\
]
. We shall denote by td
Y
(
)
variables in
Y
, and
f
i
F
X
Y
f
the transcendence
f
s
}
Fix a partition of variables
X
{
f
1
,...,
degree of
=
X
1
∈···∈
X
r
. For any polynomial
f
∗ F[
X
]
,
[
Kal
]
: F[
define the map
X
]∩Z
ↆ
0
as
⊨
r
[
Kal
]
(
f
)
=
td
X
i
(
f
).
i
=
1
The lower bound proceeds in two natural steps:
[
Kal
]
(
1. Show that
f
)
is
small
whenever
f
is computable by a
small
formula.
[
Kal
]
(
2. Show that
Det
n
)
is
large
.
[
Kal
]
for a Formula
5.3.2.1 Upper Bounding
Lemma 7
Let f be computed by a fan-in two formula
ʲ
of size s. Then for any
[
Kal
]
(
partition of variables X
=
X
1
∈···∈
X
r
, we have
f
)
=
O
(
s
)
.
Proof
For any node
v
∗
ʲ
,let
Leaf
(v)
denote the leaves of the subtree rooted
v
Leaf
X
i
(v)
v
at
and let
denote the leaves of the subtree rooted at
that are in the
ʲ
is bounded by twice the number of leaves. For each part
X
i
, we shall show that
td
X
i
(
ʲ
part
X
i
. Since the underlying graph of
is a tree, it follows that the size of
⊩
Leaf
X
i
(ʲ)
⊩
)
f
)
=
O
(
, which would prove the required bound.
Fix an arbitrary part
Y
X
i
. Define the following three sets of nodes:
V
0
=
⊞
v
∗
ʲ
:
⊩
Leaf
Y
(v)
⊩
=
=
0 and
⊩
Leaf
Y
(
Parent
(v))
⊩
ↆ
2
⊠
V
1
=
⊞
v
∗
ʲ
:
⊩
Leaf
Y
(v)
⊩
=
1 and
⊩
Leaf
Y
(
Parent
(v))
⊩
ↆ
2
⊠
V
2
=
⊞
v
∗
ʲ
:
⊩
Leaf
Y
(v)
⊩
ↆ
2
⊠
.
Each node
v
∗
V
0
computes a polynomial in
f
v
∗ F[
X
\
Y
]
, and we shall
replace the subtree at
v
by a node computing the polynomial
f
. Similarly, any node
v
V
1
computes a polynomial of the form
f
(
0
)
f
(
1
)
v
∗
+
y
for some
y
v
∗
Y
and
v
v
v
f
(
0
)
f
(
1
)
,
∗ F[
X
\
Y
]
. We shall again replace the subtree rooted at
v
by a node
v
v
computing
f
(
0
)
f
(
1
)
+
y
.
v
v
v
ʲ
Y
with leaves being
the nodes in
V
0
and
V
1
(and nodes in
V
2
are unaffected). We would like to show that
the size of the reduced formula, which is at most twice the number of its leaves, is
O
Hence, the formula
ʲ
now reduces to a smaller formula
(
⊩
Leaf
Y
(ʲ)
⊩
)
.
⊩
Leaf
Y
(ʲ)
⊩
.
Observation 8
|
V
1
| ≥
Proof
Each node in
V
1
has a distinct leaf labelled with a variable in
Y
. Hence,
|
V
1
|
is bounded by the number of leaves labelled with a variable in
Y
.
∈
(Obs)