Information Technology Reference
In-Depth Information
The classes
VP
and
VNP
in general use by Valiant and his followers differs from
them by two aspects: on one hand, there is a polynomial bound on the degree of the
polynomials in the sequence; on the other, the entries of the circuits may be labeled
by arbitrary constants, living in an unprecised loka (integers are not always sufficient,
since the inversion of 2 is essential in the celebrated proof of the universality of the
Permanent).
Various devices have been invented preventing a circuit to produce a polynomial
of exponential degree, but the truly adequate one has been defined byMalod: a circuit
is multiplicatively disjoint if each of its multiplication gates receives its two arrows
from disjoint subcircuits (note that a term is both additively and multiplicatively
disjoint). A
multiplicatively disjoint
circuit of size
c
produces a polynomial of degree
at most
c
, and in fact, when we allow arbitrary gratuitous constants, the class
VP
is
equal to the class
VPmd
of sequences of polynomials with a polynomially bounded
md-complexity (the first step of the reduction uses a computation by homogeneous
parts, renouncing to any control on the constants; see the details in [
MP06
,
MP08
]).
We shall use the class
VPmd
0
of sequences computed by multiplicatively disjoint
circuits of polynomial size, using only the constant
1, and also its termic analogue
VPt
0
; it is not known if
VPt
0
is a proper subclass of
VPmd
0
, but terms and md-
circuits are equivalent in the presence of summations; in other words
VNPmd
0
−
=
VNPt
0
; this last class is closed under taking coefficient-functions.
To study the unbounded case, Malod constructs a universal polynomial whose
coefficient-function is computable provided that the Pascaline is so. He then observes
that an old theorem of [
Luc78
] shows that the Pascaline is computable modulo
p
,
3
where
p
is a
fixed
prime number, to obtain the following results concerning
computations of polynomials with coefficients in
F
p
= Z
/
p
Z
:
(i) the class
VNPnb
0
(
mod
p
)
is closed for taking coefficient-functions
(ii) any sequence in
VNPnb
0
is obtained from a sequence in
VNPmd
0
(
mod
p
)
by replacing variables by (simply exponential) powers of variables
(iii)
VNPmd
0
(
mod
p
)
VPmd
0
VNPnb
0
(
mod
p
)
=
(
mod
p
)
∃
(
mod
p
)
=
VPnb
0
.
The right to left implication of (iii) rests on the fact that the only constants appear-
ing in a computation are the integers modulo
p
, which form a finite set.
With the help of our simpler universal polynomial, and a result of Peter Bürgisser,
we shall say more on what happens in characteristic zero.
(
mod
p
)
8.7 Characteristic Zero
Bürgisser [
Bür09
] shows that the hypothesis
VNPmd
0
VPmd
0
collapses a certain
=
hierarchy within
PSPACE
/
poly
, to which belongs the Pascaline in figures; in short,
VNPmd
0
VPmd
0
=
=
Pascfig
P/poly
.
3
If we develop the integers
m
and
n
in base
p
,
C
(
m
,
n
)
is equal modulo
p
to the product of the
binomial coefficients
C
(
u
i
,v
)
of their digits.
i
