Information Technology Reference
In-Depth Information
ʲ
,
represented as a tree (duplicating nodes if required), shall be
called a proof tree of
Such a sub-circuit
ʲ
.
Let
ProofTrees
(ʲ)
denote the set of all proof trees of
ʲ
. It is easy to see that
any proof tree of
was
a monotone circuit computing a polynomial
f
, then every proof tree computes a
monomial in
f
. Therefore,
ʲ
computes a monomial over the variables. Further, if
ʲ
⊨
[
ʲ
]
f
=
ʲ
∗
ProofTrees
(ʲ)
ʲ
. Of course, the number of proof
trees is exponential and the above expression is huge. However, we could use a
divide-and-conquer approach to the above equation using the following lemma.
[
ʲ
]
where
denotes the monomial computed by
ʲ
be a left-heavy formula of formal degree d. Then there is a node
Lemma 19
Let
ʲ
such that
d
3
2
d
v
on the left-most path of
≥
deg
(v) <
3
.
2
d
Proof
Pick the lowest node on the leftmost path that has degree at least
3
. Then,
its left child must be a node of degree less than
2
3
, and also at least
d
3
(because the
formula is left-heavy).
ʲ
and a node
[
ʲ
:
v
]
For any proof tree
v
on its leftmost path, define
to be the
output polynomial of the proof tree obtained by replacing the node
v
on the leftmost
ʲ
, define
[
ʲ
:
v
]
pathby1.If
v
does not occur on the leftmost path of
to be 0. We
will denote the polynomial computed at a node
v
by
f
v
. Then, the above equation
can now be rewritten as:
⊨
[
ʲ
]
=
f
ʲ
∗
ProofTrees
(ʲ)
⊨
⊨
[
ʲ
:
v
]
=
f
v
·
v
∗
ʲ
ʲ
∗
ProofTrees
(ʲ)
3
≥
2
3
deg
v<
⊨
⊨
[
ʲ
:
v
]
.
=
f
v
·
g
v
where
g
v
=
v
∗
ʲ
ʲ
∗
ProofTrees
(ʲ)
d
3
≥
2
d
3
deg
v<
Since
3
2
d
d
3
2
d
3
≥
v<
<
deg
g
v
≥
deg
3
, we also have that
and the last equation is
what was required by Lemma 17.
