Information Technology Reference
In-Depth Information
Linear algebra offers essentially the only fast technique for computing multivariate polyno-
mials of moderate degree.
Clearly, then, we are going to talk about polynomials, not languages or functions.
4.2 Valiant's Original Framework
Let
F
be any field, and let
F[
x
1
,...,
x
n
]
be the ring of polynomials over indeter-
minates
x
1
,...,
x
n
with coefficients from
F
. Consider a family
(
f
)
of polynomials
(
f
n
)
n
≥
1
, where each
f
n
is in
F[
x
1
,...,
x
s
(
n
)
]
for some function
s
: N −∗ N
. When
should we say that
is tractable? Clearly, if there are too many variables to keep
track of, there cannot be tractability. So we will henceforth demand that
s
is a poly-
nomially bounded function (
(
f
)
n
c
); then the
n
th polynomial
f
n
has
ↆ
c
,
≤
n
,
s
(
n
)
∈
c
+
n
c
variables. But that is of course not enough.
There are many ways in which we can set the bar for tractability. Here's a first
attempt. Can
O
(
)
be computed by a
formula
of reasonable size? To elaborate further,
a formula is an expression defined recursively:
(
f
)
1. for each
c
,“
c
” is a formula of size 0 computing the polynomial
c
,
2. for each indeterminate
x
i
,“
x
i
” is a formula of size 0 computing the polynomial
x
i
, and
3. if
F
1
,
∃ F
(
F
1
+
F
2
)
F
2
are formulas computing polynomials
f
1
and
f
2
, then “
” and
(
F
1
×
F
2
)
(
F
1
)
+
(
F
2
)
+
“
” are formulas of size size
size
1 each, computing the
polynomials
f
1
+
f
2
and
f
1
×
f
2
, respectively.
Notice that size
is just the number of ring/field operations used to construct
F
.
Instead of such a recursive definition, we could have a more intuitive picture: a
formula is a rooted binary tree where internal nodes are labelled
(
F
)
+
or
×
and leaf
nodes are labelled from the set
X
, where
X
is the set of indeterminates. The size
is just the number of non-leaf nodes.
Now, for tractability, we could require that there is a polynomially bounded func-
tion
t
F
: N −∗ N
and a family of formulas
(
F
n
)
n
≥
1
such that each
F
n
computes
f
n
and has size at most
t
. Let us use the notation VF to denote families of polyno-
mials tractable in this sense. (VF: Valiant's Formulas—of course, Valiant didn't use
this name! This class is also referred to as VP
e
: Valiant's Polynomial-sized Expres-
sions. Personally, I prefer VF. Also note, in formal logic, the formulas/expressions
referred to above are called terms, hence VF means families with polynomial “termic
complexity”. )
Here's a second attempt: Can
(
n
)
be computed by a
straight-line program
of
reasonable size? As before, we will declare polynomial size to be reasonable.
Straight-line programs are programs where instructions involve adding or multi-
plying previously computed polynomials, no divisions and no conditionals (no if-
then-else). In the more intuitive picture, they correspond to directed
acyclic
graphs
where each node is a source node (indegree 0) labelled from the set
(
f
)
F
X
, or has
