Information Technology Reference
In-Depth Information
many monomials), and each proof tree could require cutting at a different node. The
clever twist is the following: in the formula depth-reduction,
A
can be computed
recursively because it is the partial derivative of
F
with respect to
N
.If
F
is now
a circuit rather than a formula, then
F
may not be linear in
N
, so computing the
partial derivative will not help. But if
N
is chosen to have degree more than half the
degree of
F
, then this is indeed the case. So, the algorithm of [
VSBR83
] computes,
for each pair of nodes
N
N
, a new polynomial
F
N
)
,
(
N
,
; these polynomial are
N
)
N
)
recursively constructed, and whenever 2degree
equals
the partial derivative of
N
with respect to
N
. Putting this together carefully gives
the depth-required circuit. For details, see [
VSBR83
] itself. Also see [
AJMV98a
,
Vo l 9 9
]for
uniform
versions, where the task of describing the depth-reduced circuit
given the original circuit is achieved using limited computational resources.
A couple of things slipped by almost unnoticed. We know what is meant by
the degree of a polynomial, but what do we mean by degree
(
N
)>
degree
(
,
F
(
N
,
? This should be
the degree of the polynomial computed at the node
N
, and indeed [
VSBR83
]use
degree in this sense. But the uniform versions cannot do so, because computing the
degree of a specified node in a given circuit is a completely non-trivial task! See the
discussion about DegreeSLP in [
ABKPM09
,
Kay10
]. Fortunately, we can equally
easily work with an upper bound on the degree of each node. And an upper bound
u
(
N
)
(
N
)
on the degree at each node
N
is easy to obtain:
u
(
N
)
=
1if
N
is a leaf,
u
. This upper
bound is referred to as the complete formal degree of the circuit (as opposed to the
degree of the polynomial it computes). However, just because the output node of
C
computes a polynomial of degree
d
, this does not imply that each node computes a
polynomial of degree at most
d
. Higher degree monomials may get computed along
the way, and get cancelled finally. Is it necessary, in terms of efficiency, to compute
them? No! If
C
is of size
s
and computes a polynomial
f
of degree
d
, then we can
construct a circuit
C
of size
O
(
N
1
+
N
2
)
=
max
{
u
(
N
1
),
u
(
N
2
)
}
,
u
(
N
1
×
N
2
)
=
u
(
N
1
)
+
u
(
N
2
)
sd
2
computing the same polynomial and with each
node computing a polynomial of degree at most
d
: just compute the homogeneous
parts of
f
separately in the obvious way. Now
C
will have complete formal degree
O
(
)
d
3
s
. (See [
MP08
] for details.) Thus, we could have defined VP in terms of circuits
of polynomial size and polynomially bounded complete formal degree as well.
There is a much simpler proof of the fact that VP is contained in VNC. This proof
yields a weaker upper bound of VSAC
2
rather than VSAC
1
, but is still beautiful, and
is still enough to conclude that VP
(
)
VQF. I first saw this proof in a survey talk by
Koiran at Dagstuhl [
Koi10
], and I wish I had come up with it myself! Let
(
f
n
)
be
in VP, as witnessed by a circuit family
(
C
n
)
with complete formal degree bounded
by
(
d
n
)
. To depth-reduce
C
n
, partition the nodes into 1
+∅
log
d
n
⃐
parts; part
k
has
2
k
−
1
2
k
nodes with formal degree in
[
,
)
. Treating the polynomials from parts
i
<
k
as variables, the nodes in part
k
form a
skew
circuit, where each
node has at most
one child that is not an input node. (Multiplying two nodes both in part
k
would
create high degree, giving rise to a node in part
k
×
1.) Now, skew circuits can be
depth-reduced to VSAC
1
rather easily, using a divide-and-conquer argument dating
back to Savitch [
Sav70
]. Doing this separately for each part gives a VSAC
2
circuit.
+
