Information Technology Reference
In-Depth Information
the monomial will be the product of the C i : this is only a matter of matching heads
and tails.
To compute C i , let us note k the number of occurencies of i as tail; k is less than
2 n . The variables with head i are splitted in s sorts of respective degrees k 1 , ... ,
k s ,
and k
2. We must choose the k 1 i 's in
tail position that will be followed by a variable of the first kind, making C
=
k 1 + ··· +
k s ; s is smaller than i
(
i
1
)/
(
k
,
k 1 )
choices; then we must affect the variables of the second sort, making C
(
k
k 1 ,
k 2 )
choices, and so on. Taking into account the fact that C
1, which permits the
neutralization of certain binomials coefficients, we see that C i is expressible as the
product of i
(
0
,
0
) =
2 pascalines of size n , whose arguments are numbers in figures
easily computable from the degrees: they have a polynomial term complexity.
In short, the coefficient-function of P n is expressible as the product of the com-
patibility condition and of less than n 3
(
i
1
)/
i
2 pascalines of size n .
Since the coefficient-function of a polynomial of complexity n is obtained by the
following operations from the coefficient-function of P 4 n : equating to 0 the vari-
ables representing the degrees of the variables that we replace by 0, summing over
the degrees of the variables that we replace by 1 or
/
6
(
i
1
)/
1 (after a small multiplication
concerning the unique variable that we replace by
1), it is now clear that if the
Pascaline has a polynomial
-complexity of the coefficient-
function of an arbitrary polynomial is polynomially bounded in function of the
ˇ
ˇ
-complexity, then the
ˇ
-complexity of the polynomial.
8.6 A Short Review of Malod's Thesis
We shall further on follow a common (and vicious) tendency, to which we have
resisted till now, to express complexity hypothesises with the help of sequences of
polynomials, or functions, with asymptotic properties. We adopt the notations of
[ Mal03 , Mal07 ]. 1
VPnb 0 denotes the class of sequences of polynomials whose complexity is poly-
nomially bounded; V is for Valiant, P for polynomial time, nb indicates that there is
no bound on the degree of the polynomials in the sequence, and 0 indicates that
1is
the only constant that is used in the computations. Note that the class is nonuniform:
a sequence of boolean functions is in VPnb 0
poly . 2
VNPnb 0 is the class of sequences of polynomials which are obtained by a sum-
mation from a sequence in VPnb 0 ; the letter N, which is not a fortunate choice, has
been introduced in this context by Valiant as an analogy with the class NP .Wehave
shown that VNPnb 0 is closed by taking the coefficient-functions if and only if the
Pascaline belongs to it.
if and only if it is in P
/
1 We have resisted to a crave for changing them!.
2 It is customary in Valiant's calculus to use nonuniform classes, based on circuit size; were we
insist on uniformity for their Boolean counterparts, we could uniformise the Valiant's classes as
well; but for what concerns us here, uniformity would play only a decorative role.
Search WWH ::




Custom Search