Information Technology Reference
In-Depth Information
−
,
,
1.) So we can define a subclass of VP: families with constant-free circuits of
polynomial size.
What can we say about such a subclass? As described above, Bürgisser has shown
that if this subclass contains
1
0
(
Perm
n
)
, then
(
n
!
)
is easy to compute. Under the same
2
n
∞
2
2
n
e
n
hypothesis, he also shows that the sequences
ₔ
∀
,
ₔ
(
3
/
2
)
∀
and
ₔ
∀
are easy
to compute.
Malod [
Mal03
] observed that unlike in the case of VP, for constant-free circuits
we may not be able to bound complete formal degree. For VP, if the polynomial
computed by a circuit of size
s
had degree
d
, we could find an equivalent circuit
with formal degree
d
, and another with complete formal degree
O
d
3
s
, with only
polynomial blow-up in size. Not so if constants aren't freely available! Consider the
polynomial family
f
n
(
)
2
2
n
=
(
x
1
+ ··· +
x
n
)
. With arbitrary constants, we have a
1: build 2, build 2
2
n
,
build the linear form, multiply. But this circuit has exponential formal degree, and
in fact, using only the constants
circuit of size
n
. With only
−
1
,
0
,
1, we have a circuit of size 2
n
+
1, any circuit must have exponential formal
degree to build up 2
2
n
. So this polynomial is in VP, it has constant-free circuits
of polynomial size, but it does not have constant-free polynomial size circuits with
polynomially bounded complete formal degree.
This leads to a definition of a further subclass VP
0
, first defined in [
Mal03
]:
polynomial families computed by constant-free circuits with polynomially bounded
−
1
,
0
,
complete formal degree. Define VNP
0
analogous to VNP as
·
VP
0
. Check back;
is in VNP
0
.
our proof that
(
Perm
n
)
is in VNP also shows that
(
Perm
n
)
VP
0
is stronger than saying that
˄ (
(
Perm
n
)
∃
Perm
n
)
is polyno-
mially bounded. What does it imply? Can it lead to more sequences being easier to
compute? First, note that
The hypothesis
VP
0
does not immediately imply VP
0
VNP
0
.
(
Perm
n
)
∃
=
is in VP
0
, then
All we can say is the following, shown by Koiran [
Koi05
]: If
(
Perm
n
)
VNP
0
, there is some polynomially bounded function
p
for every family
(
f
n
)
∃
(
n
)
is in VP
0
. That is, a “shifted” version of
f
n
is in VP
0
.
The precise shift can be described as follows—we know that
f
n
is a projection of
Perm
q
(
n
)
2
p
(
n
)
f
n
)
such that the family
(
can be
computed by a circuit
C
n
of size and formal degree bounded by a polynomial func-
tion of
n
,wetake
p
for some polynomially bounded
q
(
n
)
, we assumed that Perm
q
(
n
)
to be the formal degree of
C
n
.Now
C
n
can be massaged to
compute 2
p
(
n
)
f
n
instead of Perm
q
(
n
)
(
n
)
.
This motivates another variant of easy-to-compute. Let's say that a sequence
a
n
)
of natural numbers is ultimately easy to compute if at least some shifted version of
it is easy to compute. That is, there is some other integer sequence
A
n
such that the
sequence
a
n
A
n
is easy to compute. Note that if
(
is not ultimately easy, then for
infinitely many
n
, all nonzero multiples of
a
n
have large
˄
complexity. Using this
property, under the hypothesis that
n
(
a
n
)
is not even ultimately easy to compute, we
can obtain a non-trivial derandomization of the Arithmetic-Circuit-Identity-Testing
problem; see the last section of [
ABKPM09
]. Earlier, Koiran showed in [
Koi05
] that if
n
!
is not even ultimately easy to compute, thenwe have some separation: either VP
0
!
=
VNP
0
,orP
PSPACE. This is curious: we have a consequence involving Boolean
classes as well. But it should not be so surprising. VP
0
and VNP
0
are computed
by (sums of) constant-free poly-formal-degree algebraic circuits, and these are the
=
