Information Technology Reference
In-Depth Information
that there are polynomial-sized straight-line programs for the symbolic determinant.
There are more direct algorithms as well; Samuelson, Berkowitz, Csanky, ... . See
[
MV97
] for an explicit description of circuits of size
O
n
4
(
)
(my favourite one—no
surprise!).
Whether the determinant can be computed efficiently by formulas (is Det
n
in
VF?) is still famously open. We know that it needs formula size at least
n
3
,see
[
Kal85
]. But we do know that it can be computed by formulas of subexponential
size 2
O
(
log
2
n
)
. This can be shown in many different ways, one of which we will look
at a bit later, but the earliest demonstration of this follows from Csanky's algorithm
[
Csa76
], which uses binary arithmetic operations and
O
ˇ(
)
log
2
n
parallel time. Thus,
if we use quasi-polynomial (2
log
c
n
for some constant
c
) formula-size as the defining
property for tractability (giving a class that we can call VQF), then again the family
(
(
)
Det
n
)
has long been known to be tractable. We could also use quasi-polynomial
circuit size as the defining property for tractability, giving a class that we can call
VQP. But VQP obviously contains VP and VQF, so
is in VQP; nothing new
there. (Note: in defining VQF and VQP, the quasi-polynomial limit on formula or
circuit size is over and above the requirement that the degree and number of variables
are polynomially bounded.)
Does VP include essentially all interesting and natural polynomial families? We
do not know. In fact, there is a large list of such polynomial families not known to
be in VP. The most natural one is the permanent family
(
Det
n
)
(
Perm
n
)
where Perm
n
is the
polynomial representing the permanent of an
n
n
matrix
A
n
of indeterminates. It
is tantalisingly similar to the determinant; just the sign term is missing.
×
n
n
Det
n
=
sign
(˃)
x
i
˃(
i
)
Perm
n
=
x
i
˃(
i
)
˃
∃
S
n
i
=
1
˃
∃
S
n
i
=
1
Yet, it does not seem to be tractable. How “intractable” is it?
Mirroring the definitions of the Boolean complexity classes P and NP, Valiant pro-
posed a notion of
p
-definability in [
Va l 7 9
]. A polynomial family
is
p
-definable
if it can be written as an exponential sum, over partial Boolean instantiations, of
another tractable family. Formally, a family
(
f
n
)
(
f
n
)
over
s
(
n
)
variables and of degree
d
are polynomially bounded, as always, and further,
there exist a polynomially bounded function
m
, and a family of polynomials
(
n
)
is
p
-definable if
s
(
n
)
and
d
(
n
)
(g
n
)
in
VF, such that
g
n
has
s
(
n
)
+
m
(
n
)
variables denoted
{
x
1
,...,
x
s
(
n
)
,
y
1
,...,
y
m
(
n
)
}
,
and
1
1
1
f
n
(
√
x
)
=
0
···
0
g
n
(
√
x
,
√
y
).
y
1
=
0
y
2
=
y
m
(
n
)
=
This looks like an algebraic analogue
·
F
, where
F
is the
class of languages decided by polynomial-size formulas. But it is well-known that
ↆ·
VF of the boolean class
ↆ·
NP, so this should be algebraic NP. Later, Valiant redefined
p
-definability
(no, that is not a circular definition!) as exponential sums of families in VP, rather
F
=
