Information Technology Reference
In-Depth Information
an addition or a multiplication; there is only one output gate, where is obtained the
polynomial computed by the circuit.
The size of the circuit is the number of its operation gates, and the
complexity
of
a polynomial is the minimal size of a circuit computing it. We note that, contrarily
to a widely admitted convention in Valiant's style calculus, we do not consider that
the constants are given for free: under our convention, if a big integer
N
is needed
for the computation of a polynomial
f
, the number of steps necessary to obtain
N
starting from the constant
1 should be included in the complexity of
f
.
A polynomial of complexity
c
has at most
c
−
1 variables; its degree is bounded
by 2
c
; it is the sum of less than 2
c
(
c
+
1
)
monomials, whose coefficients are integers
with absolute value bounded by 2
2
c
. For more details on circuits you may consult
[
Poi95
]or[
Bür00
], and the survey chapter of Meena Mahajan in this volume.
A special kind of circuits are the
terms
(some say
formulae
), of an arborescent
nature, in which each gate is allowed to throw only one arrow. The degree of a
polynomial computed by a term of size
c
is bounded by
c
+
1, and its coefficients
are bounded by 2
c
.The
termic complexity
of a polynomial is the minimal size of a
term which computes it.
Thank to the parallelization lemma of [
MP76
], terms correspond to computations
in logarithmic depth: an (arithmetic) term of size
c
can be replaced by an equivalent
circuit (or term!) of depth
O
+
, computing the same polynomial.
We also consider functions, which by definition are applications from
(
log
c
)
n
{
0
,
1
}
into
Z
; a function is
boolean
if it takes its values in
{
0
,
1
}
. It is easily seen that any function
n
of some polynomial with integer coefficients, andwe define
the complexity of the function as the minimal complexity of such a polynomial, that
is, as theminimal size of an arithmetic circuit computing the functionwhenwe restrict
its entry variables to the
{
,
}
is the restriction to
0
1
values 0 and 1. This gives a fair evaluation of
the usual complexity of a boolean function since, on one hand, one can consider the
arithmetic circuit modulo 2, and on the other addition and multiplication modulo 2
can be simulated in characteristic zero by
x
≥
boolean
∗
+
y
−
2
·
x
·
y
and
x
·
y
, respectively.
This is also the case for termic complexity, thanks to parallelization.
We use letters like
x
,
y
,
z
,...
to denote the variables in our polynomials; letters
like
u
are used for
boolean variables
, that is, variables that are assumed
to take only the values 0 and 1.
,v,w,...
8.2 Two Functions, Pascaline and Factorial
To avoid a conflict between french and english notations, we denote by
C
)
the number of subsets with
n
elements of a set with
m
elements. The
n
'th instance
of the Pascaline is the following function, depending of 2
n
(
m
,
n
+
2 boolean variables:
Pasc
n
(
, where
U
and
V
are the two numbers
whose developments in binary figures are respectively
u
and
u
0
, ... ,
u
n
;
v
0
,...,v
n
)
=
C
(
U
,
V
)
v
; in other words,
2
n
2
n
U
=
u
0
+
2
·
u
1
+ ··· +
·
u
n
and
V
=
v
0
+
2
·
v
1
+···+
·
v
n
.
We consider also the Factorial, which is defined by: Fact
n
(
u
0
,...,
u
n
)
=
!
U
.
