Information Technology Reference
In-Depth Information
ˇ
-complexity, even termic, in the first two cases, and a
minuscule one in the third. Similarly, when we reconstruct a polynomial with boolean
variables, satisfying
u
n
We have no increase of
0, there is no need to rise them to powers,
so that a summation will have only a benign effect on the
=
u
when
n
>
ˇ
-complexity, and on the
termic
-complexity, of the coefficient-functions.
We note in passing, although we shall not use this kind of operations, that replace-
ments of variables also have a mild effect: for instance, when we substitute
z
to
x
and
y
in
f
ˇ
(w)
=
u
,v
(
x
,
y
)
, to obtain
g
(
z
)
=
f
(
z
,
z
),
Cg
S
(
u
,v,w)
·
Cf
(
u
,v)
, where
S
is an easily computable boolean function taking the value 1 if
W
=
U
+
V
, and
0 if not.
There is a similar formula for the product of two polynomials, so that the
coefficient-function of a polynomial computed by a circuit of size
c
will be com-
puted by a circuit of comparable size with summation gates deeply buried in it; but in
general there is no known way to drag smoothly these summation gates at the output
of the circuit (this is possible when the circuit is multiplicatively disjoint; see the
definition in Sect.
8.6
). Circuits with summation gates define
VPSPACE
, the analog
for polynomials of
PSPACE
for boolean functions: this is the only class above the
class
VNPmd
0
(that will be defined in Sect.
8.6
) that we are certain to be closed
by taking coefficient-functions; for the details, see [
Poi08
]; see also [
KP07
] for an
approach of the class
VPSPACE
via coefficient-functions in figures.
Now the Pascaline again. Consider the polynomial
b
y
(
x
,
y
)
=
(
1
+
x
)
=
(
y
0
·
2
n
(
1
+
x
)
+
1
−
y
0
)
·····
(
y
n
·
(
1
+
x
)
+
1
−
y
n
)
, whose complexity is less than 6
(
n
+
1
)
.
)
w
=
Giving to
y
a boolean value
w
, by identification in the binomial formula
(
1
+
x
v
≤
w
)
=
v
0
,...,v
n
Cb
,v
0
,...,v
n
)
·
w
v
0
x
u
we obtain Pasc
n
(w,
Pasc
n
(w
;
u
)
·
u
(
u
·
0
··· ·
w
v
n
, so that we have an easy polynomial bound of the
ˇ
-complexity of the
Pascaline in function of the
ˇ
-complexity of the coefficient-function of
b
(
x
,
y
)
.
Note in passing that such a simple operation as the substitution of
x
by 1
+
x
may
have a drastic effect on the complexity of the coefficient-function.
In conclusion, if the
ˇ
-complexity of the coefficient-function can be polynomially
bounded in function of the
ˇ
-complexity of the polynomial, then the Pascaline has a
polynomial
-complexity; to establish the reciprocal, we shall construct in the next
section a universal polynomial whose coefficient-function has a simple expression
in function of the Pascaline.
ˇ
Remark
Since
b
is a product, its coefficient-function can be expressed as a
summation from the coefficient-functions of the factors. This give an expression,
with a summation, of the Pascaline in function of
(
x
,
y
)
2
n
n
(v)
=
C
(
,
V
)
: the Pascaline
has a polynomial
-complexity iff this is true also for this function. There is no
mystery in this reduction: it is closely related to the formula
C
ˇ
(
U
1
+···+
U
k
,
V
)
=
V
1
+ ··· +
V
k
=
V
, which generalizes Pascal's Triangle. There
is no apparent induction on
V
leading to a computation of the Pascaline with the help
of the constants
C
C
(
U
1
,
V
1
)
·····
C
(
U
k
,
V
k
)
2
i
2
j
(
,
)
.
