Information Technology Reference
In-Depth Information
equivalent bounded-width branching program (that's quite a mouthful; let's agree to
call it BWBP) of length 4
D
and width just 3! Since we already know that formulas
can be depth-reduced and VF equals VNC
1
, we see that VF is contained in a class
that we can name VBWBP: polynomial-sized constant-width ABPs. The converse
inclusion is easily seen to hold, again using a Savitch-style divide-and-conquer. Thus,
we have another characterisation of VF.
As a matter of curiosity, one may want to know: is the width-3 upper bound
tight? Allender and Wang [
AW11
] recently settled this question affirmatively: they
show that a very simple polynomial cannot be computed by any width-2 ABP, no
matter what the length. On the other hand, width-3 ABPs are universal, since every
polynomial family has some formula family computing it. The question is one of
efficiency: which families have polynomial-size width 3 ABPs?
OK, so we've had a plethora of class definitions, but just a handful of distinct
classes: VF
VNC
1
=
VP
e
=
=
VBWBP, VBP
=
VP
skew
=
VP
ws
,VP
=
VP
MD
,
VQF
VNP.
As stated in [
Bür00a
],
Valiant's hypothesis
says that VNP
=
VQP, VNF
=
VP, and
Valiant's
extended hypothesis
says that VNP
VQP. Over fields of characteristic not equal to
2, these imply: Perm
n
is not a
p
-projection of Det
n
, and Perm
n
is not a
qp
-projection
of Det
n
, respectively.
Some miscellaneous results, in no specific order:
1. Let SymDet
n
be the polynomial that represents the determinant of a symmetric
n
x
12
.)
×
n
matrix of indeterminates
B
n
. (For instance, SymDet
2
=
x
11
x
22
−
(
SymDet
n
)
(
Det
n
)
Clearly,
. The converse is also almost
true. As shown by Grenet et al. in [
GKKP11
], over any field of characteristic
other than 2, Det
n
is a projection of SymDet
n
3
. Characteristic 2 is a problem:
symmetric matrices correspond to undirected graphs, so each undirected cycle
gives rise to two directed cycles, and so to get a projection we need division by
2. In characteristic 2, Det
n
itself is provably not a projection of SymDet
m
for any
m
;see[
GMT13
]. The best that we can currently say in characteristic 2 is that the
squared determinant
is a
p
-projection of
2
is a projection of SymDet
2
n
3
(
Det
n
)
2
;thisisalsoshown
+
in [
GKKP11
].
2. VQP is also characterized by quasi-polynomial-size weakly skew circuits of poly-
nomial degree. (From [
VSBR83
] it follows that VQP
VQF; hence the above
characterization. A direct proof is presented in [
MP08
].) Several natural poly-
nomials are complete for this class under
qp
-reductions: the
=
family, of
course, but also, the trace of iterated matrix product and the trace of a matrix
power. These families are all complete for VBP under
p
-reductions.
3. While we do not know the exact relationship betweenVQP and VNP, (they both
contain VP), we do know that VQP does not equal either VP or VNP. Bürgisser
(
(
Det
n
)
in VQP that is provably not in VNP, let alone in VP. This family is defined
as follows: Consider numbers in base
n
.Let
μ
range over all such numbers with
m
f
n
)
(
n
)
=∅
log
n
⃐
digits. More precisely, let
μ
range over length-
m
(
n
)
sequences
over the alphabet
{
0
,
1
,...,
n
−
1
}
, and let
k
n
(μ)
denote the value of this sequence,
