Information Technology Reference
In-Depth Information
8.5 A Universal Polynomial
n
2
We consider the polynomial
P
n
depending of
n
(
−
1
)/
6 variables
x
ijk
, where
0
≤
k
<
j
<
i
≤
n
, which is defined by the following induction:
P
0
=
P
1
=
1
P
n
(. . .
x
ijk
,...)
=
x
ni j
·
P
i
·
P
j
{
(
i
,
j
)
|
0
≤
j
<
i
<
n
}
We say that
n
is the
head
of the variable
x
ni j
, and that
i
and
j
are its
tails
.
This polynomial, of complexity less than
n
3
/
2, is able to simulate any circuit of
size less than
n
1. To see that,
we consider circuits as straight line programs, that is, we order their gates in such a
way that each operation gate receive its two arrows from anterior gates. If we want
that
P
i
simulate an input gate labeled by the variable
x
i
10
, we equate all the other
variables of head
i
to 0. If we want to simulate the product of
P
j
and
P
k
, where
1
/
4 just by replacing some of its variables by 0, 1 or
−
i
, we equate
x
ijk
to 1 and the other variables of head
i
to 0. If we
want to simulate the addition of
P
j
and
P
k
, where 1
<
k
<
j
<
i
,we
equate
x
ij
1
and
x
ik
0
to 1, and the other variables of head
i
to 0. The only constraint
in the simulation is that we cannot multiply directly a gate by itself: we must before
duplicate it by a neutral operation, such that a multiplication by 1, tripling (yes) the
size of the circuit; note that the entry gates count in the length of the straight line
program, but not in the size of the circuit: all this explains the bound
n
<
j
<
i
and 1
<
k
<
4.
There is no need to make substitutions of variables, since we can assume that, in
a circuit, the variables are associated injectively to the input gates; but of course one
of the variable has to be replaced by
/
1.
Let us now evaluate the coefficient-function of
P
n
. When we develop brutally
P
n
,
just by distributing the product on the sum, we express it has the sum of a twice
exponential family of products of variables that we call
arborescent monomials
;the
actual expression of
P
n
as a sum of monomials is obtained by grouping together
the arborescent monomials corresponding to a same monomial, those which have
the same degree in each of the variables.
The arborescent monomials are obtained as follows: we start from a variable
x
ni j
whose head is
n
, then we multiply it by a variable of head
i
and a variable of head
j
(if possible, that is if
i
−
2), and repeat the process till we reach at the extremity
of every branch a terminal variable
x
k
01
; when the small tail is 0 or 1, but not the big
one, there is only one variable that follows.
In the following example, for
n
>
j
∈
6, we do not write the
x
's, but only their
indexes; the monomial associated to this arborescent monomial is:
=
2
3
654
.
540
.(
432
)
.
321
.
310
.(
210
)
.
