Information Technology Reference
In-Depth Information
+
×
indegree 2 and is labelled
. A designated sink node (outdegree 0) is the output
node. Each node computes a polynomial in the obvious way, and the graph computes
the polynomial at the output node. (The acyclicity constraint ensures that there is a
linear ordering of the nodes such that each node, or instruction, only uses previously
computed polynomials. This gives the straight-line program.) The size is the number
of non-source nodes; again, this corresponds to the number of ring/field operations
required. Such graphs are in fact exactly
algebraic circuits
, and we now look for
polynomial size circuit families.
Clearly, this model generalises formulas. The catch is that it generalises it too
much! To see why, consider the following circuit family:
C
n
has
n
or
+
1 nodes
v
0
,v
1
,...,v
n
, and the labeling is
v
0
=
x
1
,
v
i
+
1
=
v
i
×
v
i
for
i
∃[
n
]
. The family
x
2
n
1
of polynomials
(
f
n
)
computed by
(
C
n
)
is
f
n
=
. Even for small integer values
of
x
1
, writing down the value of
f
n
(
x
1
)
is going to require exponentially many bits.
How can we say that such a family
is tractable?
So we need to impose some additional restrictions. The obvious parameter to
restrict is the degree of the polynomial. Say that the family
(
f
n
)
(
f
n
)
hasmoderate degree if
for some polynomially bounded function
d
: N −∗ N
, the degree of each polynomial
D
is polynomially bounded, then on integer
arguments with
b
-bit representations, the value of
f
n
requires nomore than poly
f
n
is at most
d
(
n
)
.Ifdegree
(
f
n
)
=
(
n
,
b
)
bits. (In general, it needs no more than poly
(
n
,
D
,
b
)
bits.) Henceforth, to qualify for
the label tractable, a family
must have polynomially bounded degree.
(Why didn't we face this problem when considering
VF
? Simply because a for-
mula of size
t
cannot compute a polynomial of degree more than
t
(
f
n
)
+
1. Don't just
believe me; check this by induction on formula size.)
Now we have our second possible definition of tractability:
(
f
n
)
is tractable if the
sequence degree
(
f
n
)
is polynomially bounded, and there is a polynomially bounded
function
t
: N −∗ N
and a family of straight-line programs, or algebraic cir-
cuits,
. Let us
use the notation VP to denote families of polynomials tractable in this sense. (VP:
Valiant's analogue of the Boolean complexity class P. Valiant called these families
p
-computable [
Va l 8 2
]).
The well-studied polynomial family from linear algebra, the determinant of a
matrix of indeterminates, is known to be tractable in this second sense. (To define
the family
(
C
n
)
n
≥
1
, such that each
C
n
computes
f
n
and has size at most
t
(
n
)
(
Det
n
)
, imagine an
n
×
n
matrix
A
n
with a new indeterminate
x
ij
at each
position
(
i
,
j
)
, and let Det
n
be the polynomial that represents the determinant of
A
n
.
Thus Det
1
=
x
12
x
21
, and so on. Clearly, this family satisfies
the mandatory conditions: Det
n
has
n
2
variables and is of degree
n
.) This is not
surprising; we know that the determinant can be computed efficiently (in polynomial
time) over instantiated matrices using, say, Gaussian elimination. But to compute the
symbolic determinant via a straight-line program, Gaussian elimination is apparently
not directly of use because we can't search for nonzero pivots and eliminate them
(remember, no divisions and no conditionals). However, Strassen [
Str73
]gavea
generic method of converting any straight-line program with divisions to a division-
free straight-line program; the resulting program's size is polynomially bounded in
the original size, the number of variables and the degree. Thus, we can conclude
x
11
,Det
2
=
x
11
x
22
−
