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)
Search WWH ::




Custom Search