Information Technology Reference
In-Depth Information
are disjoint; in case of a squaring,
u
ϕ(
2
=
u
,v
ϕ(
variables
u
and
,
so that the computation of
ϕ
must be done twice: when we repeat
n
times, we explode.
Similarly, we can define the
v
u
)
u
)
·
ϕ(v)
-complexity, replacing summations by productions; it
is equally unclear if the Pascaline, as the Factorial, has a polynomial
ʲ
-complexity.
Apolynomial is the sumof its monomials. This basic truth explains the importance
of summations. Let us first define exponential as the following polynomial, where
y
ʲ
=
(
y
0
,...,
y
m
)
:
x
2
i
x
2
m
x
y
x
2
=
(
y
0
·
x
+
1
−
y
0
)
·
(
y
1
·
+
1
−
y
1
)
···
(
y
i
·
+
1
−
y
i
)
···
(
y
m
·
+
1
−
y
m
)
Observe that if we give boolean values to
y
, then
x
u
x
U
, where
U
is the integer
=
2
n
U
=
u
0
+
2
·
u
1
+···+
·
u
n
. In these conditions, a polynomial
f
(
x
)
depending
of
n
variables of degree at most 2
m
can be written as:
x
u
1
1
x
u
n
f
(
x
)
=
Cf
(
u
1
;
...
;
u
n
)
·
...
n
u
where Cf
(
u
)
is a function depending of
m
·
n
boolean variables, that we call the
coefficient-function of
f
.
Since polynomials correspond bijectively to their coefficient-functions, it is tempt-
ing to establish a correlation between the complexities of these two kinds of objects.
It is easy to bound the complexity of
x
y
by 6m, so that a polynomial
(
x
)
ˇ
-complexity
for the coefficient-function implies a polynomial
-complexity for the polynomial.
What about the other direction? We shall see that the Pascaline plays a crucial role
in this question.
ˇ
8.4 Operations on the Polynomials and their Effect
on the Coefficient-Functions
Given a polynomial
f
, what is the effect of a projection, i.e., of the substitution
of some of the variables by constants, on the coefficient-function? When we replace
the variable
y
by the constant
a
, how do we obtain the coefficient-function of
g
(
y
,
x
)
(
x
)
=
f
(
a
,
x
)
from the coefficient-function of
f
(
y
,
x
)
? We must reconstruct partially the
polynomial: if we note
the boolean variables describing the degree of the variable
y
,
and leave the others in the dark, Cg
v
=
v
a
v
. The substitution has therefore
Cf
(v)
·
only a polynomial effect on the
-complexity of the coefficient-functions.
This is not the case of the termic
ˇ
-complexity, since the exponential involves
a
2
n
which is obtained by a succession of
n
squarings. Fortunately enough, there are
three integers whose powers remain at a reasonable distance:
ˇ
•
=
=
(
)
a
0; Cg is the constant term, Cg
Cf
0
=
v
•
=
(v)
a
1; all the powers are equal to 1, Cg
Cf
=
•
=−
v
(
−
v
0
)
·
(v)
a
1; we change the sign according to parity, Cg
1
2
Cf
