Information Technology Reference
In-Depth Information
Csanky's result which was specifically tailored for the determinant. Further, this
algorithm has parallel multiplicative depth only
O
(
)
log
D
; that is, any root-to-leaf
path goes through at most
O
multiplication nodes. This is worth noting since
multiplication seems a more costly operation than addition or subtraction. Unfortu-
nately, the resulting circuit, while shallow and depth-reduced, is rather large, roughly
t
log
D
. Applying this construction would take us frompolynomial size circuits to shal-
low quasi-polynomial size circuits. Soon after this, an improved construction was
presented by Valiant et al. [
VSBR83
]; they achieved the same depth-reduction (and
also
O
(
log
D
)
multiplicative depth) with size polynomial in
tD
. In particular, apply-
ing this construction to a circuit family
(
log
D
)
(
C
n
)
witnessing that a polynomial family
VNC
2
.
Wait, what exactly are these new classes? Again, we can think of them as ana-
logues of Boolean classes. The Boolean circuit class NC
i
has circuits of polynomial
size and
O
is in VSAC
1
(
f
n
)
is in VP, we see that
(
f
n
)
log
i
n
depth. The class SAC
i
(
)
is similarly defined, polynomial size,
log
i
n
O
(
)
∧
-depth, and negations only at inputs. That is, if
∩
nodes are allowed
to have unbounded in-degree, but
∧
nodes must have in-degree 2, then these cir-
log
i
n
cuits have depth
O
(
)
. (Hence the name SAC, for semi-unbounded alternation.)
Clearly, NC
i
NC
i
+
1
. Now define the classes VNC
i
and VSAC
i
as alge-
braic analogues of these, with
SAC
i
×
and
+
playing the roles of
∧
and
∩
, respectively.
In the Boolean world, we know that NC
1
SAC
1
NC
2
···
NC
P. In the
algebraic world, however, VNC
1
VSAC
1
VNC
2
VP.
An important consequence of the depth reduction result of [
VSBR83
]isthatthe
=
= ··· =
VNC
=
(
Det
n
)
∃
VQF. Another important
consequence is that at quasi-polynomial size, formulas are as powerful as circuits;
VQF equals VQP. Such an equivalence is not known for
p
-families at polynomial
size. (It holds at exponential size, because polynomials in any
p
-family have only
exponentially many monomials. An explicit sum-of-monomials expression gives an
exponential-sized formula.)
Even before the results of [
Hya79
,
VSBR83
], Brent [
Bre74
] had shown that depth-
reduction is possible for VF. Any formula
F
can be rebalanced by identifying in it a
suitably chosen node
N
and rewriting
F
as a linear form in
N
,say
AN
VQF result generalises to all of VP; VP
B
.If
N
is
properly chosen, then the polynomials
A
and
B
are computed by small subformulas
(size at most half of
F
)of
F
, and can be recursively rebalanced. The appropriate
N
is identified by using the tree separator lemma. This process yields a
O
+
(
log size
(
F
))
VNC
1
.
The depth reduction for VP from [
VSBR83
] proceeds similarly, but works on
“proof-trees” or
parse trees
. Unfolding a circuit into a formula by systematically
duplicating reused nodes may yield an exponential-sized formula (recall the example
X
2
n
.) Let us nonetheless do so. Now, a minimal subformula that includes the output
node, both children of an included
depth formula. Thus, we conclude VF
=
×
node, and exactly one child of an included
+
node, computes a potential monomial whose degree is the number of leaf nodes
in the subformula. Call such a subformula a proof tree. For a circuit computing a
p
-family of polynomials, we can ignore proof trees of super-polynomial size. For
each polynomial-sized proof tree, the balancing technique described above should
work. The catch is, there can be too many proof trees (there can be exponentially
