Information Technology Reference
In-Depth Information
k
n
(μ)
=
m
(
n
)
μ
j
n
j
−
1
. Define
f
n
as:
j
=
1
m
(
n
)
2
2
kn
(μ)
x
μ
j
j
f
n
(
x
1
,...,
x
m
(
n
)
)
=
j
=
1
μ
∃{
0
,...,
n
−
1
}
m
(
n
)
Exploiting the fact that the distinct double exponentials appear as coefficients in
f
n
, Bürgisser shows that
f
n
cannot be in VNP.
Furthermore, using
m
log
i
n
gives a family of polynomials
f
i
(
n
)
=∅
⃐
in VQP
n
log
i
n
log
i
−
1
n
n
with size
O
(
)
but provably not in size
O
(
)
, so within VQP there is
a strict hierarchy.
4. From the
qp
-completeness of
(
Det
n
)
for VQP, and the
p
-completeness of
(
Perm
n
)
for VNP, it follows that VNP
VQP if and only if
(
Perm
n
)
is a
qp
-projection
of
(
Det
n
)
. This is a very long-standing open question. Originally, the question of
whether
are
p
-equivalent was posed by Pólya [
Pól13
], who
also showed that there is no way of expressing the permanent as the determinant
by only changing the signs of selected entries (except for
n
(
Det
n
)
and
(
Perm
n
)
=
2; flip the sign of
(
)
=
(
)
a
12
to get matrix
B
with Det
). (I haven't myself seen Pólya's note,
but have seen it referred to in various places.) Marcus and Minc [
MM61
]showed
that there is no size-preserving transformation (Perm
n
to Det
n
), even if we relax
the notion of projections to allow linear form substitions for each variable. For
many years, a linear lower bound was the best known (
B
Perm
A
ˇ(
∞
2
n
due to [
vzG87
,
Cai90
,
Mes89
]), until Mignon and Ressayre [
MR04
] showed that over the fields
of characteristic 0 (eg real or complex numbers), even if linear form substitutions
are allowed in projections, to express Perm
n
as a projection of Det
m
, we need
m
)
n
2
2. The same lower bound was obtained for fields of characteristic other
than 2 by Cai et al. [
CCL10
]. From Ryser's work [
Rys63
] it follows that Perm
n
is
a projection of Det
m
for some
m
≥
/
n
2
2
n
. More recently, Grenet showed [
Gre12b
]
via a very simple and neat construction that Perm
n
is a projection of Det
m
for
m
<
2
n
1. This is the best known so far. Thus there is a huge gap between the
lower and upper bounds on what is called the determinantal complexity of the
permanent.
5. It is natural to believe that the complexity of a
p
-family
=
−
in this framework
is closely related to the computational complexity of
evaluating f
n
for a given
instantiation of its variables. In [
Bür00b
], Bürgisser gave this belief a firm footing.
Consider a
p
-family
(
f
n
)
(
f
n
)
where
f
n
depends on
n
variables. Define its Boolean part
n
BoolPart
(
f
)
as a string function mapping
x
∃{
0
,
1
}
to the binary encoding of
. Note that we have considered onlyBoolean values. Even so, evaluationmay
seem difficult, because the circuits for
f
n
(
x
)
(
f
n
)
can involve arbitrary constants from
the field. Bürgisser showed that assuming the generalised Reimann hypothesis
GRH, over fields of characteristic zero, BoolPart
has non-uniform multi-
output NC
3
circuits. Furthermore, assuming GRH, if Valiant's hypothesis is false
over such a field, then the entire polynomial hierarchy has (non-uniform) NC
circuits.
(
VP
)
