Malod and the Pascaline - Perspectives in Computational Complexity - page 152

Let us remind that, by the Parsimonious Reduction Lemma, to any boolean func-
tion f

( )

, computed by an arithmetic circuit modulo 2 of complexity c , is associated
a boolean function g

u

( u ,v) , computed by an arithmetic termmodulo 2 of size 4 c , such

that, if f ( u ) = 0, then g ( u ,v) = 0 for every v , and if f ( u ) = 1, then g ( u ,v) = 0

for every v , except for one for which it takes the value 1 (the length of v is equal to c ,

and the exceptional corresponds to the values that are computed at the gates of the

circuit). After parallelization, the computation of g can be simulated in characteristic
zero by a term of small complexity, and, because of the uniqueness of the exceptional
v

v

is obtained by a summation in front of this last term (we do not claim that
there is a way to simulate in characteristic zero summations in characteristic 2; see
[ Poi ]). As a consequence, any sequence of boolean functions which is in VPnb 0 ,
i.e., in P/poly ,isin VNPmd 0 .
Assume that VNPmd 0

, f ( u )

VPmd 0 . If, in the expression of the Pascaline as a
summation from the Pascaline in figure we replace the numbers 2 2 i by variables y i ,
we obtain therefore a (sequence of) multilinear polynomial(s) in VNPmd 0 ;using
a second time our hypothesis, we see that this polynomial is in VPmd 0 , and, after
substitution of the y i by the adequate powers of 2, that the Pascaline is in VPnb 0
(we remind that this implies an easy factorization). This is more than enough for
VNPnb 0 to be closed for the coefficient-function.
Moreover, in the expression of a polynomial as the summation of its monomials,
we can also replace the power x 2 j

=

i of a variable x i by a new variable x ij . From our
description of the coefficient-functions of the projections of the universal polynomial,
we conclude that any sequence of polynomials in VNPnb 0 is obtained by plugging
in a sequence in VNPmd 0 simply exponential powers of 2 and of variables. We reach
the same conclusion as Malod in characteristic p , this time not as a fact, but as a
consequence of an hazardous hypothesis.
The conclusion is that VNPmd 0

VPmd 0

implies VNPnb 0

VPnb 0 .

= =

VPnb 0 , VNPmd 0 is included in
VPnb 0 ; since a polynomial in VNPmd 0 has a small degree, a computation by homo-
geneous parts truncates its VPnb -computation into a small multiplicatively disjoint
circuit, which unfortunately may use at its entry gates some twice exponential inte-
gers: we know no way to get rid of these big numbers.
Nevertheless we should keep in a corner of our mind that all these hypothesizes
are probably equivalent, and false!

The reciprocal is problematic: if VNPnb 0

=

References

[Bür00] P. Bürgisser, Completeness and Reduction in Algebraic Complexity Theory. Number 7 in
Algorithms and Computation in Mathematics . (Springer, Berlin, 2000)
[Bür09] P. Bürgisser, On defining integers and proving arithmetic circuit lower bounds. Comput.
Complex. 18 (1), 81-103 (2009)
[KP07] P. Koiran, S. Perifel, VPSPACE and a transfer theorem over the complex field, Proc.
MFCS, LNCS 4708 , 359-370 (2007)