A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant

A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a lamaniere de ValiantAuthor(s): Bruno PoizatSource: The Journal of Symbolic Logic, Vol. 73, No. 4 (Dec., 2008), pp. 1179-1201Published by: Association for Symbolic LogicStable URL: http://www.jstor.org/stable/27590326 .

Accessed: 16/06/2014 03:09

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .http://www.jstor.org/page/info/about/policies/terms.jsp

.JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range ofcontent in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new formsof scholarship. For more information about JSTOR, please contact [email protected].

.

Association for Symbolic Logic is collaborating with JSTOR to digitize, preserve and extend access to TheJournal of Symbolic Logic.

http://www.jstor.org

This content downloaded from 195.78.109.162 on Mon, 16 Jun 2014 03:09:15 AMAll use subject to JSTOR Terms and Conditions

http://www.jstor.org/action/showPublisher?publisherCode=asl

http://www.jstor.org/stable/27590326?origin=JSTOR-pdf

http://www.jstor.org/page/info/about/policies/terms.jsp


The Journal of Symbolic Logic Volume 73. Number 4. Dec. 2008

A LA RECHERCHE DE LA DEFINITION DE LA COMPLEXITE D'ESPACE POUR LE CALCUL DES POLYNOMES A LA MANIERE DE

VALIANT

BRUNO POIZAT

R?sum?. Nous d?finissons une classe de suites de polyn?mes, calcul?s par des circuits de complexit?

polynomiale comprenant des additions, des soustractions, des multiplications et des sommations de Valiant.

Nous montrons que cette classe est close pour la prise de la fonction-coefficient d?finie au paragraphe 3 de

cet article ; nous en d?duisons l'existence d'un circuit de complexit? 72.?", calculant le coefficient binomial

de deux nombres de n chiffres, donn?s en base 2. Il est par ailleurs facile de construire un circuit de

complexit? 17.? + 2 calculant la factorielle d'un nombre de n chiffres. La pr?sence de l.n sommations

d'effet exponentiel dans chacun de ces circuits en affecte gravement l'int?r?t pratique. Il est peu probable, ou du moins peu souhaitable, qu'on puisse ?liminer ces sommations sans explosion, car cela provoquerait la catastrophe cryptographique que redoutent tous les banquiers ; n?anmoins, nous ne savons pas s?parer la classe d?finie ici de celle des suites de polyn?mes calculables en un nombre polynomial d'op?rations

arithm?tiques. Cela n'a rien de surprenant, vu la tr?s grande affinit? qu'elle a avec la classe PSPACE : nous

montrons en effet que cette classe est identique ? la classe VPSPACE. d?finie ant?rieurement par Koiran et

Perifel, qui appara?t ici sous une forme bien plus maniable que l'originale.

?1. Classes de complexit?, fa?on Valiant. Dans cette section liminaire, nous rap pelons la d?finition des objets utilis?s pour l'?tude de la complexit? de calcul des

polyn?mes ? la mani?re de Valiant, et nous pr?cisons les conventions que nous

adoptons. Pour plus de d?tails sur le sujet, on pourra consulter [B?rgisser, 2000]. Un circuit arithm?tique C est un graphe orient? fini, sans cycles orient?s, ? une

seule sortie, dont les entr?es sont ?tiquet?es par des variables ou par des constantes, et dont les autres sommets, appel?s portes, re?oivent exactement deux fl?ches et sont

?tiquet?s par l'addition, ou bien par la multiplication. Le sous-circuit Cp associ? ? la porte p est form? des portes de C situ?es sur un chemin arrivant ? p.

Sauf de mani?re ?pisodique, nous n'employons que la constante ? 1. Contrairement ? ce que conviennent certains, nos circuits arithm?tiques ne font

pas de divisions ; ils d?composent les soustractions en une multiplication par la constante ?1 suivie d'une addition.

Nous distinguons deux sortes de variables ; les premi?res ne prennent que les valeurs 0 ou 1 ; elles sont qualifi?es de bool?ennes, bien que leur valeur soit un

entier, et non pas un entier modulo 2 ; les autres variables sont libres de prendre les valeurs de leur choix.

Received January 5, 2007.

Mots-clefs. Polyn?mes, circuits arithm?tiques, complexit?, op?rations, quantifications. P et PSPACE, Valiant.

? 2008. Association for Symbolic Logic 0022-4812/08/7304-0006/S3.30

1179



1180 BRUNO poizat

S'il n'y a pas de variables bool?ennes, le circuit calcule un polyn?me f(x) a

coefficients entiers relatifs. S'il y en a, il calcule ce que nous appelons une fonction

polyn?me, qui au uplet bool?en u associe un polyn?me fu_(x_). que nous pouvons tout aussi bien noter f(u.x). Si le circuit ne comporte pas de variables non

bool?ennes, ce polyn?me est une constante, et nous parlerons alors de fonction

num?rique. Une fonction num?rique est dite bool?enne si elle ne prend que les valeurs 0 ou 1.

Toute fonction-polyn?me a pour origine un polyn?me dont on a sp?cialis? bool?ennement certaines variables. Cela se montre facilement par r?currence sur

la longueur de u, en it?rant la formule f(u_,v.x) =

v.f(u. L x) + (1 ?

v).f(u, 0. x). Ce polyn?me n'est bien s?r pas unique, puisque seules comptent les valeurs qu'il prend lorsque ses variables bool?ennes parcourent l'ensemble {0.1}. Comme nous mesurons la complexit? de calcul d'une fonction-polyn?me par la complexit? mini male d'un polyn?me dont elle provient, les questions qu'on se posera ? propos des

fonctions-polyn?mes seront toujours ?quivalentes aux questions correspondantes concernant les polyn?mes.

La complexit? c du circuit C est par d?finition son nombre de portes d'addition et de multiplication ; son nombre de fl?ches est l.c, si bien qu'il n'a pas plus de c + 1

entr?es, puisque chacune de ses portes, sauf sa sortie, ?met au moins une fl?che.

La profondeur p de C est la longueur maximale d'un chemin joignant une entr?e ? la sortie ; elle est inf?rieure ? c, qui est elle-m?me major?e par lp. Son ampleur est le nombre entier calcul? par le circuit obtenu ? partir de C en ?tiquetant toutes ses entr?es par la constante 1 = (? l)2 ; l'ampleur majore la somme des valeurs absolues des coefficients des mon?mes du polyn?me calcul? par C ; elle est inf?rieure ?2A2^; <2A2C.

Le degr? de C est calcul? par le circuit obtenu ? partir de C en ?tiquetant ses entr?es

par 1 (qu'elles soient variables ou constantes), en rempla?ant ses multiplications par des additions, et ses additions par des prises de maximum ; le degr? est major? par lp, lui-m?me inf?rieur ? Ie. Le sous-degr? de C est d?fini de la m?me mani?re que son degr?, sauf qu'une entr?e ?tiquet?e par une constante se voit attribuer le sous

degr? 0. On notera bien que les variables bool?ennes sont prises en compte comme les autres dans l'?valuation du degr? et du sous-degr?. Autrement dit, le degr? de C est celui du polyn?me calcul? par le circuit obtenu

en rempla?ant la constante -1 par une variable : pour d?finir le sous-degr? de cette

mani?re, on remplace cette constante ?

1 par la constante 1.

Il est clair que le sous-degr? de C majore le degr? (total) du polyn?me qu'il calcule. R?ciproquement, si un polyn?me de degr? d est calcul? par un circuit de

complexit? c, le calcul de ses parties homog?nes permet de l'exprimer par un circuit de complexit? c.(d + l)2 et de sous-degr? d.

Le remplacement du sous-degr? par le degr? est par contre plus acrobatique. Si dans un circuit de sous-degr? d et de complexit? c on remplace chaque porte de

sous-degr? nul par une entr?e ?tiquet?e par l'entier relatif qu'elle calcule, on obtient un circuit de complexit? moindre et de degr? inf?rieur ? cd +1 (voir [Malod, 2003]). Mais cette manipulation suppose qu'on emploie librement des constantes enti?res,

d'ampleur doublement exponentielle, puisque borner le sous-degr? ne bride pas le calcul des constantes, ce ? quoi nous nous refusons ici, bien que le don gratuit de constantes arbitraires soit commun?ment admis chez les disciples de Valiant.



LE CALCUL DES POLYNOMES A LA MANIERE DE VALIANT 1181

La classe de complexit? ch?rie par ce dernier est celle o? l'on borne polynomiale ment ? la fois la complexit? et le degr? du circuit, et pour nous ce sera bien son degr?, et non pas son sous-degr?. Guillaume Malod a compris tout l'avantage qu'avait la

possibilit? de d?finir cette classe en bornant polynomialement un seul param?tre du circuit, sa complexit?, ? condition d'imposer une condition structurelle ? son

architecture. Il a d?fini la notion de circuit multiplicativement disjoint, pour lequel chaque porte de multiplication re?oit ses fl?ches de deux sous-circuits disjoints. Un

circuit multiplicativement disjoint de complexit? c a son degr? major? par c + 1, tandis que son ampleur est inf?rieure ? 2e. R?ciproquement, un circuit de com

plexit? c et de degr? d peut se remplacer par un circuit multiplicativement disjoint de complexit? cd, qui calcule le m?me polyn?me (voir [Malod, 2003], [Malod and

Portier, 2006]). Enfin, les termes sont les circuits qui sont ? la fois additivement et multiplicative

ment disjoints ; le lemme de parall?lisation de [M?ller and Preparata, 1976] ?tablit

l'?quivalence des circuits de profondeur logarithmique et des termes de complexit? polynomiale.

Tout cela m?ne ? la d?finition des classes de suites de fonctions-polyn?mes sui

vantes, qui chacune ne d?pend que d'un nombre polynomial de variables : -

VPdl, l'ensemble des suites /? de fonctions-polyn?mes calcul?es par une suite

Cn de circuits arithm?tiques dont la complexit? est major?e par un polyn?me en n

- VPdb, l'ensemble des suites /? de fonctions-polyn?mes calcul?es par une suite

C? de circuits arithm?tiques dont la complexit? est major?e par un polyn?me en n, ainsi que leur sous-degr? (ou, de fa?on ?quivalente, le degr? des po

lyn?mes /?) -

VPmd, l'ensemble des suites /? de fonctions-polyn?mes calcul?es par une

suite Cn de circuits arithm?tiques multiplicativement disjoints dont la com

plexit? est major?e par un polyn?me en n (ou, de fa?on ?quivalente, par une

suite de circuits arithm?tiques de complexit? et de degr??pas de sous-degr?? polynomialement born?s)

- VPt, l'ensemble des suites /? de fonctions-polyn?mes calcul?es par une suite Cn de termes arithm?tiques dont la complexit? est major?e par un polyn?me en n

(ou, de fa?on ?quivalente, par une suite de circuits arithm?tiques de profondeur

logarithmique). VPt est incluse dans VPmd, mais on ne sait pas si cette inclusion est stricte ; il s'agit de la variante polynomiale du c?l?bre probl?me de parall?lisation des algorithmes (p =?NCi) ; toutefois la classe VPmd se parallelise en profondeur polylogarith

mique, d'apr?s [Valiant, Skyumi, Berkowitz, and Racko?f, 1983]. Par contre VPdl contient strictement VPmd ; en effet, le degr? et le logarithme de l'ampleur d'une suite dans VPdl peuvent ?tre exponentiels, tandis que dans VPmd ils restent poly nomiaux.

Quant ? la classe VPdb, qui est strictement comprise entre VPdl et VPmd pour des raisons de degr? et d'ampleur, elle n'a pas beaucoup d'int?r?t.

La lettre V rend hommage ? Leslie Valiant, et indique que les objets calcul?s sont des polyn?mes, et non pas des fonctions bool?ennes ; P est pour (complexit?) polynomiale, t pour terme, md pour multiplicativement disjoint, db pour degr? born? et dl pour degr? libre. A strictement parler, ces classes ont ?t? introduite



1182 BRUNO POIZAT

par [Malod, 2003], qui utilise des notations un peu diff?rentes ; en particulier il

emploie le signe ? pour indiquer que

? 1 est la seule constante utilis?e, ce dont nous nous abstenons puisque chez nous c'est une convention syst?matique. Les travaux

originaux de Valiant ont pour cadre une classe d?finie de fa?on semblable ? VPdb, ? ceci pr?s qu'est autoris? l'emploi gratuit de constantes rationnelles (dans ce cas, comme les constantes autoris?es forment un anneau, VPdb(Q)

= VPmd(?)).

Nous d?finissons maintenant les sommations de Valiant. Soit f(u,v.x) une

fonction-polyn?me, dont uq?v forment les variables bool?ennes, et x les variables non-bool?ennes. Nous appelons sommation de Valiant l'op?ration

^v?{QA}Anf(??> V--> ?)> dont le r?sultat est une fonction-polyn?me qui ne d?pend plus du uplet de variables bool?ennes v. Si v est vide, on convient que l'op?ration est

neutre, S0/(m,x) =

f(u,x). En appliquant une sommation de Valiant devant chaque point des suites appar

tenant aux classes VPt, VPmd, VPdl, on obtient respectivement les classes VNPt, VNPmd, VNPdl. Il est connu que, sous une sommation de Valiant, circuits multipli cativement disjoints et termes sont ?quivalents, c'est-?-dire que VNPt = VNPmd ; c'est une ?tape essentielle de la preuve du c?l?bre th?or?me de Valiant sur la

compl?tude du permanent pour la classe VNPmd (qui demande l'emploi de la constante 1/2 ; voir [Valiant, 1979]) ; on en trouvera une d?monstration tr?s concep tuelle dans [Malod, 2003].

Par contre, on ne sait pas s?parer VNPmd de VPmd : c'est la question fondamen tale pos?e par Valiant (c'est en fait une variante un peu plus stricte de cette question, puisque nous n'autorisons que -1 comme constante) ; on ne sait pas d'avantage

s?parer VNPdl de VPdl. Les ?galit?s VNPmd = VPmd et VNPdl = VPdl. ou m?me la seule inclusion

de VNPmd dans VPdl, semblent toutefois bien improbables, car elles impliquent P = # P, et en cons?quence P = NP (ou plus exactement la version non-uniforme de ces assertions, puisqu'il n'est pas dans l'usage d'introduire de conditions d'uni formit? dans la d?finition des classes de complexit? de Valiant). Pour le voir, on utilise tout d'abord la r?duction parcimonieuse des circuits bool?ens aux termes bool?ens (voir les d?monstrations des Lemmes 6 et 10) ; on mime ensuite par des termes arithm?tiques une quelconque suite fn (u) de termes bool?ens de complexit? polynomiale, et on observe que leur somme de Valiant exprime le nombre de solu tions de l'?quation /? (u)

= 1 ; comme ce nombre est simplement exponentiel, son calcul dans VPdl se remplace par un calcul en chiffres dans P.

La lettre N est pour non-d?terminisme ; comme l'ont remarqu? plusieurs auteurs, ce choix n'est ici pas tr?s heureux, ? admettre qu'il le soit dans le cas de la complexit? classique, bool?enne ; en effet, il n'y a pas de vraie analogie de comportement entre la classe NP et les classes VNP, qui sont ? rapprocher plut?t de la classe #P. En

particulier, si on borne le degr?, les sommations ne produisent pas de hi?rarchie, comme le montre le Th?or?me 2 qui suit. Apr?s r?flexion, nous n'avons pas chang? cette notation ?tablie par l'usage, d'autant plus qu'il y a un parall?le entre les classes VNP et NP qui sera expos? dans la derni?re section de cet article.

Remarque 1. Les classes de complexit? bool?ennes non-uniformes sont usuelle ment munies du suffixe /poly, que n'emploie pas l'auteur de ces lignes pour protester contre la d?marche absurde qui consiste ? introduire de l'uniformit? par un disposi tif combinatoire aussi compliqu? qu'une machine de Turing pour ensuite la d?truire



LE CALCUL DES POLYNOMES A LA MANIERE DE VALIANT 11 83

par un artifice : dans tous les r?sultats expos?s ici, l'uniformit? n'aurait qu'un effet d?coratif parasite, sans rapport avec le fond du probl?me. Il trouve par ailleurs incoh?rent de mettre de l'uniformit? aux classes bool?ennes et pas ? celles de Va

liant, et s'engage ? attacher du /poly aux classes bool?ennes quand les f?tichistes de r?flectivit? en accrocheront aussi aux classes de Valiant.

?2. Les circuits S-arithm?tiques. Dans la d?finition des classes VNP la somma

tion de Valiant n'est appliqu?e qu'une fois, ? la sortie du circuit. Nous introduisons maintenant des sommations partout dans les calculs, et pour cela nous consid?rons

des circuits que nous qualifions de S-arithm?tiqLies (S = sommations ; nous dirons aussi S-circuits) et qui, en plus des portes d'additions et de multiplication, com

portent des portes de sommation, qui ne re?oivent qu'une seule fl?che, et effectuent une sommation relative ? un certain uplet v de variables bool?ennes.

La complexit? du circuit est par d?finition son nombre de portes d'addition, de

multiplication et de sommation : son nombre d'entr?es est major? par la somme

de son nombre de portes d'addition et de son nombre de portes de multiplication, augment?e d'une unit?.

L'ensemble des variables libres associ?es ? une porte p d'un S-circuit est d?fini de mani?re inductive et obvie ; si p est une entr?e index?e par

? 1, cet ensemble est vide :

si p est une entr?e index?e par une variable, cet ensemble est le singleton de cette

variable : si p est une addition, p =

pf + p"\ ou bien une multiplication, p ?

p'' .p"', cet ensemble est la r?union de r ensemble des variables libres de p' et de celui de p" ; si p est une sommation E^,//, son ensemble de variables libres est celui de p' priv? de y_.

Nous exigeons qu'une sommation porte sur un uplet de variables libres ? la

porte p' ; cette exigence n'est pas tr?s forte, car en trois op?rations on peut ajouter

puis retrancher une nouvelle variable v ? la fonction-polyn?me calcul?e en pf ; elle ?vite d'avoir ? tenir compte, dans l'?valuation de la complexit?, du nombre de variables de sommation qui n'appara?traient pas aux entr?es du circuit. Une autre fa?on de faire serait de n'introduire que des sommations portant sur une seule variable : une sommation sur n variables, devant ?tre d?compos?e en n sommations

successives portant sur une variable, se verrait alors attribuer la complexit? n.

Une suite de fonctions-polyn?mes est dite dans VSPdl si elle est calcul?e par une

suite de circuits S-arithm?tiques de complexit? polynomiale ; si on contraint ces

circuits ? ?tre multiplicativement disjoints, ou bien ? ?tre des termes, on obtient

respectivement les classes VSPmd et VSPt. Comme une sommation n'affecte pas le degr? et multiplie l'ampleur par un

nombre simplement exponentiel, il n'y a pas de s?paration ?vidente entre une classe VSP et la classe VNP correspondante. Cependant, ces sommations dispers?es dans le circuit n'apportent rien de nouveau si on borne le degr?, car nous allons voir que, si ce circuit est multiplicativement disjoint, on peut faire remonter toutes les som

mations en une seule, effectu?e ? la sortie, au prix d'une augmentation polynomiale

de la complexit? : autrement dit VSPmd = VNPmd(= VSPt = VNPt). Dans un S-circuit. une m?me variable peut avoir ? la fois des occurrences libres et

des occurences li?es : c'est une chose qu'il est impossible de corriger radicalement si le circuit n'est pas un terme. L'inconv?nient, c'est que si v est li?e dans le calcul de f(u. v). on ne calcule pas f(u. 1) en rempla?ant v par 1 = (?l)2 aux entr?es du



1184 BRUNO poizat

circuit ; de m?me, on n'obtient pas f(w,w)cn rempla?ant u et v par w aux entr?es du circuit. Mais par bonheur, une sommation de Valiant permet de faire, pour un faible

co?t, un changement de variables bool?ennes non pas aux entr?es, mais ? la sortie du circuit, gr?ce aux formules f(u. 1)

= Hvv.f(u.v), f(u.O)

= Zv(l ?

v).f(u,v), f(w,w)

= T,u.v((u ?

w)2 ?

l).((v ?

w)2 ?

\).f(u,v). Ce co?t est effectivement tr?s faible car si, apr?s avoir calcul? g(u), on veut k exemplaires suppl?mentaires g(v\),... ,g(vk) de cette fonction, la formule g(v)

= ZM(?l).((v + (-l).u)2 +

(?l)).g(u) permet de les obtenir avec une complexit? qui augmente de 1k, au lieu d'?tre multipli?e par k + 1.

Nous avons adopt? la convention de distinguer des variables bool?ennes des

autres, ? qui il est interdit d'appara?tre sous une sommation ; elle nous permet de montrer facilement que la classe VSPdl est close par composition, les remplacements de variables bool?ennes par des fonctions bool?ennes pouvant se faire ? la sortie au lieu de se faire ? l'entr?e : si les variables x et y pouvaient jouer un r?le bool?en dans les sommations et un r?le non-bool?en par ailleurs, on ne pourrait d?duire un

calcul de f(z, z) a partir d'un calcul de f(x, y) ni par remplacement aux entr?es, ni par changement de variable ? la sortie !

Cependant, cette convention n'est pas co?teuse. Si on ne la fait pas, c'est-?-dire si

on tol?re qu'une variable x puisse appara?tre sous une sommation SxG{0.i}

et prenne

ailleurs des valeurs arbitaires, pour s'y ramener il suffit de remplacer aux entr?es x

par u.x + v, o? u et v sont des variables bool?ennes ; on remplace Hxf(x,y) par

SM,V(1 -

u).f(u.x + v,y), et on se d?barasse de u et de v ? la sortie gr?ce ? une

sommation I,u,vu.(l ?v).f(u.x + v,y). Cette manipulation n'a qu'un effet b?nin sur

la complexit? des circuits, et ne change pas la d?finition de la classe VSPdl. Comme elle n'affecte pas la disjonction des multiplications, elle conserve ?galement la classe VSPmd et l'?galit? VSPmd = VNPmd.

Ce pouvoir miraculeux qu'ont les sommations de Valiant de dupliquer gratui tement, ou presque, les fonctions de variables bool?ennes va ?tre utilis? si souvent

que nous ?valuons d?s ? pr?sent le nombre d'op?rations n?cessaires pour changer le nom de n variables bool?ennes dans une fonction. La formule est / (v\,..., vn )

?

I^y_(-l)n.((ui ?

v\)2 -

1).((un ?

vn)2 -

\).f(u\,... ,un)\ chacun des facteurs

(uj + (-l).Vj)2 + (? 1) demande quatre op?rations; il faut ensuite effectuer leur

produit avec f(u), ce qui demande n multiplications, multiplier ?ventuellement par ? 1 et faire la sommation ; cela fait en tout 5n + 1 ou 5n 3-1 op?rations, suivant la

parit? de n. Le changement de variables bool?ennes nous permet de nous ramener ? des S

circuits satisfaisant une contrainte particuli?re. Nous dirons que le S-circuit C est

r?gulier si, ? chacune de ses portes p, une variable u qui est libre en p n'appara?t jamais comme variable de sommation dans le sous-circuit Cp. Autrement dit, re

lativement ? une porte p d'un circuit r?gulier, les variables se r?partissent en trois

groupes disjoints : les variables qui sont li?es dans le circuit Cp ; celles qui sont libres en p ; celles qui ne figurent pas aux entr?es de Cp.

La r?gularit? sera utilis?e dans la d?monstration du Th?or?me 2 pour faire sauter les sommations par dessus les additions ; supposons qu'on sache calculer f(u), et

que nous voulions calculer / (u)+f (0)+f ( 1 ) = / (u) 3-T,uf (u) en peu d'op?rations suppl?mentaires, mais en mettant la sommation ? la sortie du circuit ; comme u est ?




la fois libre et li?e ? la sortie, nous devons d'abord changer cette variable bool?enne en une autre, v, gr?ce ? la formule f(v)

= EM(1 ?

(u ?

v)2).f(u), et finalement

f(v) + f(0) + f(\) = EM(2

? (u

? v)2).f(u), ce qui n'ajoute que huit op?rations,

dont la sommation de sortie, au calcul de f(u). Pour calculer f(u) + f(0) + f(\), il n'y avait qu'? pr?voir la bonne variable au d?part ! Aucune formule de ce genre ne permet de calculer f(u).(f(0) + f(l)) : nous ne ferons sauter les sommations

par dessus les produits que dans les circuits multiplicativement disjoints, gr?ce au

Th?or?me de Fubini, qui demande que les ensembles de variables de sommation des deux facteurs soient disjoints.

Lemme 1, de R?gularisation. Un S-circuit C, de complexit? c,peut se remplacer

par un S-circuit r?gulier C*, de complexit? 10.c2, qui calcule la m?me fonction polyn?me. Si C est multiplicativement disjoint, on peut obtenir C* multiplicativement disjoint de complexit? \4.c2.

D?monstration. Pour chaque porte p calculant la fonction p(u), le circuit C* contient une porte p* calculant la m?me fonction, mais dans un jeu de variables u*

diff?rent, et qui lui est propre ; nous ne mentionnons que les variables bool?ennes, car on ne touche pas aux autres, et nous notons n leur nombre.

La construction de C* se fait par induction sur la profondeur du sous-circuit Cp. On ne change rien aux entr?es.

Si p est une porte de sommation, p(u) =

Y<^p'(u, v), la porte p'* d?j? construite calcule p'(u*,v*) dans un nouveau jeu de variables ; il nous faut effectuer la som mation sur v*, et changer le nom des variables survivantes de u *, ce qui se fait en une seule sommation et au plus 5^ + 2 op?rations.

Si p est une porte d'addition ou de multiplication, p = p' + p" ou p = p' .p", il nous faut d'abord exprimer les fonctions calcul?es en p"" et p"* dans un nouveau

jeu de variables avant de les additionner ou de les multiplier, ce qui demande au

plus 2.(5/7 + 2) + 1 = lO./? + 5 op?rations. Comme nous avons introduit des variables nouvelles ? chaque porte p*, C* est

r?gulier ; pour qu'il calcule la fonction demand?e, il n'y a qu'a pr?voir que ses

variables de sortie soient les bonnes. Le nombre de variables est major? par le nombre d'entr?es, qui l'est par c + 1 ;

mais si le circuit C a c + 1 entr?es, il ne comporte pas de sommation et le r?sultat est ?vident ; si le circuit a c entr?es et comporte une sommation, c'est un terme, et pour le r?gulariser il suffit de changer le nom des variables de sommation ? ses entr?es. Et s'il n'y pas plus de c - 1 entr?es, la complexit? de C* est major?e par c.(\0.(c

- 1) + 5)

= lO.c2 - 5.c < lO.c2. Si C est multiplicativement disjoint, et si on veut que C* le reste, il faut effectuer les

multiplications auxiliaires de mani?re disjointe, c'est-?-dire calculer les expressions (uj

- Vf)2

= (uj ?

Vi).(uf -

Vf) en cinq op?rations au lieu de trois, ce qui ajoute l.n ? la complexit? des changements de variables. La complexit? de C* est alors born?e

parc.(14.(c-l) + 5) < 14.c2. H

Ce lemme et le th?or?me suivant montrent que VSPmd = VNPmd.

Th?or?me 2. Si C est un circuit S-arithm?tique multiplicativement disjoint et

r?gulier de complexit? c, on peut construire un circuit arithm?tique multiplicative ment disjoint de complexit? l.c2, calculant une fonction-polyn?me f(u,y_,x) dont la sommation de Valiant T^vf(u, v, x) est la fonction-polyn?me calcul?e par C.



1186 BRUNO PO IZA I

D?monstration. On suppose que c > 2. car le th?or?me est ?vident pour c ? 0

et pour c = 1.

L'id?e est d'utiliser le Th?or?me de Fubini. qui d?clare que (î?f (u)).(^f (v)) =

û.iif(y)-f('^ Quand les uplets uetv sont disjoints. Cependant, comme une m?me

variable peut ?tiqueter des entr?es diff?rentes, le fait que le circuit soit multiplicative ment disjoint n'implique pas qu'? une porte de multiplication les uplets de variables

de sommation soient disjoints. Nous rem?dions ? cela en introduisant un nouveau

uplet y de variables?une variable par entr?e ?tiquet?e par une variable?et nous no

tons s la surjection canonique de y sur les variables de C : s (y' ) = s (y") signifie donc

que les entr?es index?es par y' et par y" sont ?tiquet?es dans C par la m?me variable. Nous construisons, par induction sur la profondeur, un circuit arithm?tique

multiplicativement dispoint C*. comprenant, pour chaque porte p de C. une porte

/?* calculant p* (u. :).o?w est l'ensemble des variables de y dont l'image par s est li?e

? la porte p. et r est l'ensemble des variables de y dont l'image par s est libre ? la porte

p, telle que Z?/?*(w. s(z_)) soit la fonction-polyn?me calcul?e dans C ? la porte p. Si p est une entr?e index?e par

? 1, /?* aussi : si p est une entr?e index?e par s (y). /?* est une entr?e index?e par y.

Si p est une porte de produit, p =

p'.p". les fonctions pf*(u'.z_f) et p//*(u/,.z_,/)

n'ont pas de variables en commun puisque C est multiplicativement disjoint, et /?* est tout simplement le produit de /?'* et de p"*. ?a reste multiplicativement disjoint.

Si p est une porte d'addition, p = pf + p", la r?gularit? de C impose qu'aucune variable de if n'apparaisse dans r". ni aucune variable de u" dans ?. Si nous

notons w la r?union de w7 et de w", et r celle de z'_ et de;", nous posons p*(u.z_) =

U' .pf*(d.?) + U".p"*(uff.z_"), o? U' est le produit des variables de w" qui ne sont

pas dans if, et U" celui des variables de u[ qui ne sont pas dans w" ; ces facteurs servent ? ?viter qu'apr?s sommation p'* (uf .z_') et p"* (u".z_") soient multipli?s par des puissances intempestives de 2. S'il n'y a pas plus de n variables, ce calcul ne

demande pas plus de n + 1 op?rations, avec multiplications disjointes. Supposons maintenant que p soit une porte de sommation, recevant sa fl?che

de p' : la fonction-polyn?me calcul?e en pf* d?pend des variables u_, v et z_, o? les

variables de v sont celles dont l'image par s intervient dans la sommation en p.

Puisque C est r?gulier, s ne peut identifier une variable de u et une variable de v.

La fonction-polyn?me p*(u. v. z_) s'obtient en faisant passer v du c?t? de u, ? ceci

pr?s qu'il faut restreindre la sommation aux v tels que v\ = v2 si s(v\) = s(v2) :

pour ce faire on multiplie p'*(u. v. z) par des facteurs du type (v\ ?

v2)2 ? 1, qui est

nul si v\ ̂ v2 : comme on doit disjoindre les multiplications, chacun de ces facteurs demande 6 op?rations, et en jouant sur la transitivit? de l'?galit? on n'a pas besoin

d'en mettre plus de n ? 1 : on a peut-?tre besoin d'une multiplication par ? 1 pour

que le r?sultat soit 1. et non pas ? 1, quand toutes les ?galit?s sont v?rifi?es, si bien

que pour effectuer ce produit il ne faut pas plus de 1 .(n - 1 ) + 1 = l.n-6 op?rations.

Comme n > 2.1 .n ? 6 > n + 1.

Si le circuit C a c t 1 entr?es, il n'a pas de portes de sommation, et C* = C (au

changement de variables pr?s !). Sinon, n est major? par c. et la complexit? de C*

par c.(l.c -

6) = l.c2

? 6.c < l.c2.

Pour obtenir le circuit cherch?, on remplace les variables libres ? la sortie de C*

par leurs images par s. H




?3. La fonction-coefficient. La fonction-coefficient du polyn?me f(x\,... .xn) est ainsi d?finie : si y_x,..., y_n sont les ?critures en base deux des entiers d\._dn,

cf(u.\^'^V.n) est le coefficient dans / du mon?me x\ Ad\.a'/7 Ad?. On peut aussi d?finir des fonctions-coefficients partielles, en consid?rant / comme un polyn?me en un sous-ensemble de l'ensemble de ses variables, la fonction-coefficient d?pendant alors des autres variables ; c'est ainsi que, pour une fonction-polyn?me, on consid?re

en g?n?ral sa fonction-coefficient par rapport ? ses variables non-bool?ennes. Nous consid?rons ?galement le polyn?me r?duit de /. qui est obtenu de la

mani?re suivante. Si x est une variable, xd = x A (ô + 2.v\ + + 2m~l.vm-\) =

xv0.(x2)vl_(x A 2m~l)vm~l ; nous introduisons, pour chacune de ces variables x

(non-bool?enne) un m-uplet de nouvelles variables jo,..., ym-\, et dans l'expres sion de chaque mon?me nous rempla?ons xA2' par y i. Ce polyn?me r?duit a m?me fonction-coefficient que / ; il est de degr? un par rapport ? chacune de ses variables non-bool?ennes, et / s'obtient ? partir de son polyn?me r?duit en y rempla?ant des variables par des puissances de variables.

Dans chacune des classes de complexit? que nous consid?rons, le nombre de variables est polynomial et le degr? au pire simplement exponentiel, si bien que les fonctions-coefficients ne d?pendent que d'un nombre polynomial d'arguments, et

qu'il est raisonnable de chercher ? ?valuer leur complexit?. Si v =

(vo,... ,vm-\), nous notons x- le produit des v,-.(x A 21 ? 1) + 1 ; ce

polyn?me se calcule en 5.m - 1 additions et multiplications (1 ?

(-1)2 n'est calcul?

qu'une fois !) ; si v prend une valeur bool?enne, x- est la puissance de x par l'entier d dont v est le d?veloppement binaire. Comme un polyn?me est somme de ses

mon?mes, f(x) =

Ei;c/(tj. ....

vn).x\ Av{.xn A y_n, si bien que, si la suite cfs est dans VNPdl, il en est de m?me de la suite f s. La m?me chose vaut pour la classe VNPmd, car alors le degr? est petit, et le circuit calculant x- est de profondeur logarithmique. Malod a montr? que, r?ciproquement, la classe VNPt = VNPmd est close pour la

prise de fonctions-coefficients (et en cons?quence la prise de polyn?mes r?duits !), et qu'en fait l'hypoth?se VNPmd ?

VPmd ?quivaut ? la cl?ture de VPmd pour la prise de fonction-coefficient ([Malod, 2003]) : il a ?t? pr?c?d? en cela par un r?sultat de [Valiant, 1982], qui ne peut parler que du coefficient d'un mon?me isol? dans un d?veloppement partiel d'un polyn?me, faute d'avoir introduit des variables bool?ennes.

On ne sait pas si la classe VNPdl est close pour la prise de fonctions-coefficients. Par contre, c'est le cas pour la classe VSPdl. comme le montre le th?or?me suivant :

Th?or?me 3. Soit C un S-circuit de complexit? c > 0, ayant n variables non bool?ennes dont le degr? de chacune s'?crit avec m chiffres. Sa fonction-coefficient peut se calculer par un S-circuit de complexit? 22.c.m.n < 22.(c + l)3, n'ayant pas

plus de 2.c portes de sommation.

D?monstration. Nous allons construire, par induction sur la profondeur, un

S-circuit C* contenant, pour chaque porte d'op?ration p de C, une porte p* cal culant la fonction-coefficient du polyn?me calcul? en p : nous rappelons que ce

polyn?me est consid?r? comme d?velopp? en mon?mes par rapport ? ses variables non-bool?ennes seulement, les variables bool?ennes intervenant dans l'expression des coefficients de ces mon?mes. Pour exprimer la fonction-coefficient, il faut n.m



1188 BRUNO POIZAT

variables bool?ennes suppl?mentaires, mais ce jeu de variables d?pendra de /?* : il ne sera pas fixe, et m?me nous en changerons souvent.

Nous rappelons que le changement de n.m variables bool?ennes dans une fonction demande 5.n.m + 2 op?rations, dont une sommation.

Il nous faudra simuler polynomialement l'addition de deux nombres de m chiffres, ?crits en base deux. Si on additionne deux nombres x et y de un chiffre, on obtient un nombre de deux chiffres, rt, o? t est la somme modulo deux de x et de y, et o? r

est la retenue ; r = x.y, t = x + y ?

2.xy, ce qui se calcule en 4 op?rations (sommes et produits) si on pr?voit d'ajouter au circuit une porte calculant ?2 = (?1) + (?1).

Si on additionne trois nombres de un chiffres x, y et z, on obtient ?galement un

nombre de deux chiffres rt ; la retenue est la fonction-majorit? de x, y et z, qui vaut r = xy + yz + zx ? 2.xyz ; la somme modulo deux vaut t = x + y + z ? 2.(xy +

yz + zx) + A.xyz ; leur calcul demande 12 op?rations (qui dit mieux ?), ? condition de pr?voir une porte de plus calculant 4 = (?2)2.

Nous ne ferons ces additions de nombres de m chiffres que dans la situation o? la derni?re retenue est nulle, et n'a pas besoin d'?tre calcul?e ; une telle addition en

chiffre demande donc 4+12. (m ?

2)+ 10= 12.m ? 10 additions et multiplications, sans compter les deux portes calculant les constantes -2 et 4 qu'il ne faudra pas oublier d'ajouter.

Cela ?tant dit, nous construisons C* :

Premier cas. p est une porte d'addition, recevant ses fl?ches de p' et de p".

Supposons d'abord que p' et p" soient toutes deux des portes d'op?ration ; si

p"" et p""" expriment leurs fonctions-coefficients dans le m?me jeu de variables

(par exemple si p' =

p"), il suffit de les additionner; sinon, avant de ce faire, on commence par remplacer le jeu de variables de p"* par celui de p"" ; tout ceci demande au plus 5.nm + 3 op?rations.

Supposons maintenant que p' soit une porte d'op?ration et p" une entr?e ?tiquet?e par la constante -1. On gardera le m?me jeu de variable v?j, 1 < i < n, 0 < j <

m-\, que pour la fonction calcul?e en p'*, et on modifiera son coefficient constant en lui ajoutant (-1 ). (? 1 )mn .H(vj? -1 ), ce qui demande 2.nm ou 2.nm +1 op?rations.

Si p" est ?tiquet?e par une variable bool?enne, on ajoute cette derni?re au coef ficent constant, au lieu de lui ajouter ?1, en 2.nm + 2 op?rations.

Si p' est une porte d'op?ration et p" une entr?e index?e par la variable Xk non

bool?enne, on garde le m?me jeu de variables et on augmente d'une unit? le degr? du mon?me Xk en ajoutant Vk\.(?\)nm~lXlij?k\(vij

? 1), ce qui ne demande pas

plus de 2.nm op?rations. Enfin, si p' et p" sont deux entr?es, le polyn?me calcul? par p est de la forme

a + b, x + a, 2.x ou x + y, o? a et b valent -1 ou une variable bool?enne ; il n'a pas

plus de deux mon?mes ; comme la fonction caract?ristique d'un nm-uplet bool?en

(celle qui vaut 1 pour ce uplet et 0 pour les autres) se calcule en 2.nm op?rations, sa

fonction-coefficient se calcule en au plus A.nm + 3 op?rations. La contribution maximale d'une porte d'addition ? la construction de C* est

donc de 5.nm + 3 portes, dont une porte de sommation.

Deuzi?me cas. p est une porte de sommation, recevant sa fl?che de pf ; si cette derni?re est une entr?e, le polyn?me calcul? en p est de la forme ? 1, 1, u ou x, et la fonction-coefficient de ce mon?me s'exprime en 2.nm + 1 op?rations.




Si p' est une porte d'op?ration, p* fait la m?me sommation que p.

Troisi?me cas. p est une porte de multiplication, recevant ses fl?ches de p' et p".

Si p' et p" sont des entr?es, p calcule un mon?me de la forme ab, ax, x2 ou xy, dont la fonction-coefficient se calcule en l.nm + 2 op?rations.

Si p' est une porte d'op?ration et p" une entr?e ?tiquet?e par -1, on se contente de multiplier par

? 1 la fonction calcul?e en p'"". De m?me, si p" est ?tiquet?e par une variable bool?enne, on multiplie par cette variable.

Si p' est une porte d'op?ration et p" une entr?e ?tiquet?e par la variable xk, il faut augmenter d'une unit? les degr?s en cette variable ; pour cela, on introduit de nouvelles variables uk pour remplacer les variables y_k exprimant la puissance de xk et on calcule

^{vk/vk+\=uk}P'* (> U.k- )> l'expression y_k + 1 = uk signifiant que si on ajoute 1 au nombre exprim? en binaire par vk on obtient le nombre exprim? par uk. Pour restreindre la sommation ? cet ensemble, nous devons d'abord simuler l'addition de 1 ? un nombre de m chiffres, ce qui se fait en 4.m op?rations (on additionne m fois deux nombres de un chiffre), puis effectuer le remplacement des m coordonn?es de y_k + 1 par celles de u_k, ce qui demande 5.m + 2 op?rations. La contribution de la porte p est alors de 9.m 3-1 op?rations, dont une sommation.

Reste le cas o? p' et p" sont deux portes d'op?rations ; nous commen?ons par exprimer la fonction calcul?e en pff* en un jeu de variables fra?ches w_, disjoint de celui qui est utilis? en p'*, ce qui demande 5.nm + 2 op?rations; il nous faut ensuite calculer le produit de convolution p*(u)

= Z{v.w/v+w=u}Pf* (y) -P*'* (m) ,

la sommation ?tant restreinte aux (v_.w_) tels que la somme du ?-uplet d'entiers

repr?sent? par v et du n-uplet d'entiers repr?sent? par w_ donne celui repr?sent? par u. Pour cela, il nous faut d'abord effectuer les n additions en chiffres au prix de ll.nm ? 10.n op?rations, faire le produit de p"" et de p"*, et enfin changer les coordonn?es de v + w_en celles de u en 5.nm + 2 op?rations.

La contribution de cette porte de multiplication est donc de ll.nm - 10.? + 5

op?rations, dont deux sommations, ce qui est le maximum de ce que nous avons

obtenu puisque nous pouvons supposer que nm > 1, le cas n = 0 ?tant trivial. Le S-circuit C* ne comprend pas plus de l.c portes de sommation, et sa complexit?

est major?e par c. (ll.nm ? 10.n + 5) + 2, les deux derni?res portes servant ? calculer

les constantes ?2 et 4. Cette quantit? est inf?rieure ? 11.en.m, et on obtient la derni?re majoration en majorant n par c + 1 et m par c + 2. 3

Remarque 2. Il est facile d'adapter la d?monstration du Th?or?me 3 pour en obtenir une du r?sultat de Malod d?clarant que la classe VNPmd est close pour la

prise de fonction-coefficient.

?4. Pascaline et Factorielle. Nous appelons Pascaline.; (/v, v_) la fonction num?ri

que qui au deux ?-uplets bool?ens u et v de longueur n associe le coefficient binomial

CN M =

(nm), o? N est l'entier dont le d?veloppement binaire est u, tandis que M est l'entier dont le d?veloppement binaire est v. Le Th?or?me 3 a pour cons?quence que la Pascaline est dans VSPdl. En effet :

Th?or?me 4. Pasc?line? se calcule par un circuit ^-arithm?tique de complexit? 11.n2, comprenant l.n portes de sommation.



1190 BRUNO POIZAT

D?monstration. La Pascaline est intimement li?e ? la fonction-coefficient

Cu(u.v.w_) du polyn?me (x + y)11, o? u est un ?-uplet bool?en ; v est le ?-uplet bool?en repr?sentant le degr? de la variable x, et w celui qui repr?sente le degr? de la variable y. Plus pr?cis?ment, Pascaline/7 (u. v)

= Cn(u.v,u

? v), o?u~v est le

r?sultat de la soustraction en chiffres de v ? u (qui vaut 0 si u < y_). Le polyn?me (x + y)l? est le produit des Mz = 1 + u?.((x + y) A 2l - 1), pour

0 </'<? ? 1 ; il est calculable en 5.n op?rations. En rempla?ant c par 5.n,m par n

et n par 2 dans le r?sultat du Th?or?me 3, on majore la complexit? de Cn par 220.n2. Nous allons examiner de plus pr?s l'algorithme de calcul de C? pour am?liorer la constante.

Nous calculons tout d'abord la fonction-coefficient CzG??, wz-) de (x + y) A 2l,

chaque fois dans un jeu de variables neuf. Pour celle de x+y, nous formons le produit des (v{)i

? l).(woi

? l) pour/ < 0, que nous multiplions par ôo+ôo?2. ôoôo, ce qui

demande 4.? op?rations, compte non tenu du calcul de la constante ?2 ; ensuite,

pour calculer les puissances de x + y, on fait n - 1 multiplications successives, chacune contribuant pour 44.? - 15 op?rations au calcul des coefficients; cette

?tape demande donc A.n + (44.? ?

15)(? ?

1) + 2 = 44.?2 ? 55.? + 17 op?rations (les deux derni?res portes calculent ?2 et 4). dont 2.(?

? 1) sommations.

Comme M/ ? u\.(x + y) A 2' + ( 1

? ul ), pour obtenir la fonction-coefficient raz- de

ce dernier, on multiplie c? par u? et on augmente son coefficient constant de 1 ? m en

lui ajoutant (?l).(u? ?

l).Yl(v?j ?

l).(w?j ?

1), ce qui demande 4.? +4 op?rations. Comme il y a ? fonctions ?i, ? calculer, ?a fait en tout 4.?2 + 4.? op?rations ? cette

?tape. Nous introduisons de nouvelles variables v et w pour calculer le produit de

convolution E2?0.f...+]?/2_i^. wQ+---+wn-i=wc(v0,wQ).cn-\(vn_x, wn__{) ; il nous

faut pour cela effectuer deux additions de ? nombres de ? chiffres, ce qui demande

2.(? ?

1).(12.? ?

10) ? 24.?2 ? 44.? + 20, les constantes ?2 et 4 ayant d?j? ?t?

calcul?es. Ensuite il nous faut calculer la fonction caract?ristique de l'ensemble sur

lequel porte la sommation, puis effectuer cette derni?re, ce qui revient ? changer 2.? variables bool?ennes, soit 10.? + 1 op?rations.

Pour r?sumer, le calcul de la fonction C? demande 44.?2 ? 55.? +17 + 4.?2 + 4.? +

24.?2-44.?+20+10.? + l = 72.?2-85.?+38op?rations,dont2.(?-l) + l = 2.?-l sommations.

La Pascaline est donn?e par la formule Pascaline? (u. v) = ^{w/v+w=u} Cn (M, y_, w). Il faut 12.? ?10 op?rations pour l'addition, et 5.?+2 pour la fonction caract?ristique et la disparition de y?, dont une sommation.

La Pascaline se calcule donc en 72.?2 - 68.? + 30 op?rations, dont 2.? sommations de Valiant. H

Nous introduisons ?galement la fonction Factorielle?, qui ? un n-uplet bool?en associe la factorielle du nombre dont il est la repr?sentation en base deux. Il est bien connu que. si on sait calculer la Pascaline, on sait aussi calculer la Fac

torielle, ce qui met ?galement cette derni?re dans VSPdl ; l'id?e est d'utiliser la formule (2.N)?

= C^N .(N!)2 : comme la suppression du premier chiffre d'un

nombre ne le divise pas exactement par deux, la formule de r?currence est la sui vante :Factorielle?+i(wo- u\_- un)

? Pascaline;7+i(0. u\,... ,un\u\,..., w?,0).(l +

uq.(2m\ + + 2?.w?)).Factoriellen(wi,.... un)2. En appliquant cette m?thode,




compte tenu de notre ?valuation de la complexit? de la Pascaline. on obtient un

circuit S-arithm?tique de complexit? 15jv\ comportant moins de (n 3- l)2 somma tions de Valiant, qui calcule Factorielle,,. Nous ne d?taillons pas la construction de ce circuit car il est facile d'en donner un

bien meilleur qui fait le m?me calcul. Pour le voir, nous introduisons deux nouvelles d?finitions : une ?valuation est l'op?ration qui au polyn?me f(x.u) associe le

polyn?me f(x_. 0). ou bien le polyn?me f(x. 1 ) : une production est une op?ration du type nw6{o.i}A/7/Cv- u). Comme dans le cas des sommations, les productions se

d?composent en productions unaires.

Evaluations, sommations et productions se simulent les unes les autres en pr?sence des op?rations arithm?tiques, et de la constante ? 1. Cela est d? aux formules :

/'(O) = 1,(1

- u).f(u), /'(I) - ZmW./"(w) : f(0) =

n,[(l -

u).f(u) + w], f(\) =

Uu[u.f(u) + 1 - u] : IM/(w) = /(O) + /(l) : ITM/(w) = /(0)./(l). En cons?quence, les suites de circuits de complexit? polynomials comportant des

portes binaires d'addition et de multiplication, et des portes unaires de sommation, ou des portes unaires de production, ou des portes unaires d'?valuation, ou les trois

? la fois, d?finissent la m?me classe de suites de polyn?mes, celle que nous avons

appel?e VSPdl ! Nous avons choisi de la d?finir ? partir de la sommation, op?ration naturelle si on consid?re qu'un polyn?me est somme de ses mon?mes, qui en outre

permet d'en distinguer la sous-classe VNPdl et d'?noncer notre Th?or?me 2. On

peut penser toutefois, au vu de l'usage constant que nous avons fait des changements

de variables bool?ennes, que les ?valuations sont plus naturelles. Comme la Factorielle s'exprime facilement par une production, on majore sa

complexit? avec une ?gale facilit? :

Th?or?me 5. Factoriellen se calcule en 13.n -f- 2 op?rations arithm?tiques et une

production, qu'on peut remplacer par l.n sommations et 4.n op?rations arithm?tiques :

cela donne un circuit S-arithm?tique de complexit? 17.? + 2, comportant l.n somma

tions de Valiant.

D?monstration. Factorielle,, (w) = nr[/(w.;i?).(-l + vo + l.v\ -f +

l"~l.vn-\) 3- 1], o? f(u.v) est un polyn?me qui vaut 1 si l'entier repr?sent? par u est sup?rieur ou ?gal ? celui repr?sent? par v. et 0 sinon. On peut prendre pour / le terme fn de la suite d?finie par la relation de r?currence suivante : fo

= 1,

// +i =

fj.[l3-(l-(un-[-vn-\)2). ...

.(\-(ut1-i-vn-i)2).(un-j-l-l).vn-i-l], le polyn?me /,- valant 1 si le nombre d?fini par les / chiffres de t?te de u est sup?rieur ou ?gal ? celui d?fini par les / chiffres de t?te de v. et 0 sinon. Il est alors calculable en 11 .n +1 op?rations, d'o? le premier r?sultat. Le second vient de ce qu'une production unaire se simule par deux sommations et quatre op?rations arithm?tiques. H

Il est tr?s peu probable, ou ? tout le moins catastrophique pour la cryptographie ? clef publique, que la Factorielle. et en cons?quence la Pascaline, soient dans VPdl. car. comme il est bien connu, si la Factorielle se calcule en peu d'op?rations on peut rapidement factoriser les nombres ?crits en chiffres : en effet, on d?termine si N a un facteur premier inf?rieur ? M en calculant le pgcd de N et du reste modulo N de M! : si la Factorielle est dans VPdl. cela repr?sente un calcul faisable en chiffres : en quelques ?tapes on localise le plus petit facteur premier de N. et finalement on le factorise.



1192 BRUNO POIZAT

Cela milite en faveur de l'in?galit? VSPdl ^ VPdl. Par contre, la pr?sence de la Pascaline ou de la Factorielle dans VNPdl ne semble pas avoir de cons?quences aussi dramatiques, ce qui permet d'envisager avec moins d'effroi la possibilit? de la cl?ture de la classe VNPdl pour la prise de fonction-coefficient, ou m?me l'?galit? de VSPdl et de VNPdl.

Le seul fait de consid?rer des fonctions num?riques conduit ? se poser la question de savoir si une hypoth?se du type VS(ou N) P = VP ?quivaut ? sa restriction aux fonctions num?riques (ou m?me aux suites num?riques, qui sont les fonctions

num?riques d?pendant de 0 variables). Plus pr?cis?ment, on peut se demander si la Pascaline et la Factorielle sont universelles pour la classe VSPdl, relativement ? une

forme de r?duction qui reste ? d?finir.

Enfin, ?tant donn? le r?le essentiel que jouent les soustractions dans nos calculs, il est peu probable qu'on puisse les ?liminer ; mais il ne sera peut-?tre pas facile de

r?pondre ? la question suivante : est-ce que la Pascaline et la Factorielle sont cal culables par des circuits S-arithm?tiques de complexit? polynomiale, qui n'utilisent

que la constante 1 au lieu de la constante ? 1 ?

Remarque 3. Il n'y a qu'un nombre simplement exponentiel de circuits S

arithm?tiques de complexit? ?, si bien qu'un simple argument de diagonalisation fabrique des suites d'entiers de croissance doublement exponentielle qui ne sont pas dans VSPdl ; plus pr?cis?ment, on peut trouver une suite d'entiers positifs a? < 2 A2" tels que, pour ? assez grand, an ne soit pas calculable par un circuit S-arithm?tique

de complexit? inf?rieure ? ?log^).

Remarque 4. Il est peu probable que nos calculs de la Factorielle pr?sentent un

quelconque int?r?t pratique ; en effet, ils utilisent les sommations de Valiant pour obtenir plusieurs jeux de la m?me fonction, sans avoir ? refaire le calcul : cela semble bien peu r?aliste. Dans la sommation du changement de variable, ? chaque v fix? il

n'y a qu'une valeur de u pour laquelle la fonction que l'on somme sur u n'est pas

nulle, si bien que toute tentative de calcul de cette sommation par ?chantillonage (la somme est le produit de la moyenne par 2n, o? ? est le nombre de variables de

sommation) aboutit ? la fonction nulle. De m?me, le calcul du produit de convolution fait intervenir une sommation portant sur un ensemble n?gligeable. On n'oubliera

pas que la probl?matique des classes de complexit? n'est pas de construire des mod?les de calcul r?alistes, mais plut?t des mod?les de calcul permettant de poser des questions significatives sur la r?alit? des calculs ; ce n'est pas tout-?-fait la m?me chose.

Remarque 5. La plupart des auteurs qui ?tudient le calcul de la Factorielle, ou d'autres fonctions num?riques, les consid?rent point par point. Ce serait une

chose bien remarquable qu'il existe un polyn?me p(n) tel que, pour tout entier N, le nombre N! se calcule ? partir de ? 1 en p(log(N)) op?rations arithm?tiques ; mais on ne pourrait en d?duire sans pr?cautions que la Factorielle est dans VPdl. Ce qu'on pourrait en d?duire, c'est que tout nombre de ? chiffres, pris individuellement, se

factorise en un temps polynomial en ?, ce qui est absolument ?vident puisqu'il suffit de se donner les facteurs. Autrement dit, le probl?me de la factorisation ne peut se

poser que si on introduit des variables bool?ennes.




?5. Les r?sultats de Malod en caract?ristique p. Pour ?tudier les fonctions coefficients de la classe VNPdl, Malod, dans [Malod, 2003], introduit un gigan tesque polyn?me VNPdl-universel, dont l'expression de la fonction-coefficient fait intervenir des bo?tes noires calculant la Pascaline. Il observe que, si p est un nombre

premier fix?, un th?or?me de Lucas datant de la fin du 19? si?cle permet de calculer en temps polynomial le reste modulo p de la Pascaline (pour la Factorielle, c'est ?vident car il est nul si N > p).

Si donc on calcule non pas des polyn?mes ? coefficients entiers, mais des poly n?mes ? coefficients dans le corps F^

= Z / pZ, on voit que VNPdl (mod p) est

close pour la prise de fonctions-coefficients. En outre, Malod observe que la fonction-coefficient de son polyn?me

VNPdl (mod p) -universel est dans VNPt(mod p), si bien que toute suite de VNPdl(mod p) s'obtient ? partir d'une suite de VNPmd(mod p) en rempla?ant des variables par des puissances simplement exponentielles de variables. Il en

d?duit ce r?sultat remarquable : pour chaque nombre premier p fix?, l'hypoth?se VNPdl (mod p) = VPdl (mod p) ?quivaut ? l'hypoth?se VNPmd (mod p) = VPmd (mod p).

Apr?s avoir remarqu? que toute hypoth?se du type VP = VS(ou N) P implique, par un simple passage au quotient, sa contrepartie modulo p, nous ajoutons ? ces

r?sultats un modeste suppl?ment. Lemme 6. En caract?ristique p, toute fonction num?rique qui est dans

VNPdl (mod p) est dans VNPmd (mod p).

D?monstration. La d?monstration s'inspire du lemme facile et bien connu de r?duction parcimonieuse des circuits aux termes (NP = NPt, et #P = #Pt). Il suffit de montrer qu'une suite de fonctions num?riques qui est dans VPdl est dans VNPmd. Soit C(u) un circuit arithm?tique ? variables bool?ennes ; pour chaque q ^ 0 dans F^

= Z /p Z, on fabrique un terme arithm?tique Tq(u, v), de complexit? polynomiale en celle de C, tel que : si C(u)

= q,Tq(u,v)

? q pour une seule valeur de v, et 0 pour les autres; si C(u) ^ q, Tq(u,v_)

= 0 pour tout v. Le uplet v

repr?sente les valeurs qui sont calcul?es aux portes de C, si bien que la construction de ce terme demandera un codage binaire des ?l?ments de F^, par exemple par des

(p ?

l)-uplets bool?ens du type (1,..., 1,0,..., 0). Le circuit C(u) calcule la m?me fonction queE^Ti(w, v) + + Tp-\(u,y). H

Une fois qu'on sait que la classe VNPdl (mod p) est close pour la prise de

fonctions-coefficients, les autres r?sultats de Malod suivent ais?ment de ce lemme. En effet, si /? est une suite dans VNPdl (mod p), la suite de ses polyn?mes r?duits

est, d'apr?s le lemme, dans VNPmd ; comme /? s'obtient par substitution de puis sances simplement exponentielles de variables dans son polyn?me r?duit, on voit que

VNPdl(mod p) = VPdl (mod p) ?quivaut ? VNPmd (mod p) = VPmd(mod p). On obtient ?galement ceci :

Th?or?me 7. En caract?ristique p, VSPdl(mod p) =

VPdl(mod p) si et seule ment si cette hypoth?se est v?rifi?e par les fonctions num?riques et en outre

VNPmd (mod p) = VPmd(mod p).

D?monstration. D'un c?t?, VSPdl = VPdl implique VNPdl = VPdl et

VNPdb = VPdb; mais, en caract?ristique p, puisqu'il n'y a qu'un nombre fini



1194 BRUNO poizat

d'entiers modulo p, VPdb = VPmd, si bien qu'on obtient VNPmd = VPmd.

R?ciproquement, la premi?re hypoth?se implique que la fonction-coefficient d'une suite de VSPdl est dans VPdl, donc dans VNPmd. et son polyn?me r?duit aussi. La deuxi?me hypoth?se met ce dernier dans VPmd. 3

Nous allons voir que l'hypoth?se VSPdl(mod p) = VPdl(mod p) ?quivaut ?

celle du probl?me algorithmique majeur du d?but de notre si?cle ; elle est donc tr?s

improbable. La cl?ture de la classe VNPdl (mod p) pour la prise de fonctions-coefficients peut

inciter ? consid?rer favorablement l'hypoth?se VSPdl(mod p) = VNPdl(mod p) ;

elle semble toutefois presque aussi peu probable que sa version de caract?ristique nulle.

?6. Koiran et l'effondrement hypoth?tique du calcul de la Factorielle. Nous reve nons ? la caract?ristique nulle.

Pascal Koiran a ?t? le premier, semble-t'il, ? ?valuer l'incidence, sur la complexit? de calcul de certaines suites num?riques, de combinaisons d'hypoth?ses portant sur des classes de complexit? ? la Valiant et d'hypoth?ses portant sur des classes de

complexit? classiques, c'est-?-dire bool?ennes. C'est ainsi que, dans [Koiran, 2004], il montre entre autres choses que, si VNPmd = VPmd et P = PSPACE, alors la Factorielle est calculable en un nombre polynomial d'op?rations arithm?tiques, c'est-?-dire qu'elle est dans VPdl.

A strictement parler, Koiran montre un r?sultat un peu plus faible, puisqu'il cal cule les nombres N! individuellement. Ce n'est qu'un point de d?tail, car il est facile de voir que ses arguments sont valides uniform?ment pour tous les nombres de n chiffres ; et de toutes fa?ons, nous allons montrer ici que ses hypoth?ses n'entra?nent

pas seulement l'effondrement du calcul de quelques suites, mais bien l'effondrement de la classe VSPdl toute enti?re.

La classe P (non uniforme !) est form?e des suites de fonctions bool?ennes cal culables en un nombre polynomial d'op?rations ; comme cette d?finition ne d?pend pas du choix des op?rations de base, il s'agit de la classe VPdl(mod 2) restreinte aux fonctions num?riques.

Nous voyons aussi appara?tre la classe PSPACE des suites de fonctions bool?ennes calculables en espace polynomial. Sous sa version non-uniforme, elle est constitu?e

des suites de fonctions bool?ennes calcul?es par une suite de circuits de complexit? polynomiale, comprenant des portes d'addition et de multiplication modulo deux, ainsi que des portes unaires de quantifications existentielles : (3u)f(x.u) vaut 1 s'il existe un u (bool?en) tel que f(x. u)

? 1, et 0 sinon ; cette op?ration se simule dans Z/2Z par 1 + (1 + /(0)).(1 + /(!)), tandis que /(O) = (3u)(\ + u).f(x, u) et f(\)

= (3u)u.f(x. u). A la place de quantifications existentielles, on peut aussi

bien utiliser des ?valuations, ou des sommations, ou des productions (ces derni?res

repr?sentent des quanteurs universels). Autrement dit la classe PSPACE est la classe

VSPdl(mod 2) restreinte aux fonctions num?riques. Parmi les mille et une fa?ons de d?finir PSPACE, nous avons choisi celle qui nous

convient le mieux : elle est justifi?e par la PSPACE-compl?tude de l'?valuation des formules avec quantifications.




La d?finition de PSPACE ? partir des circuits comportant des portes d'addi tion et de multiplication modulo 2, ainsi que des portes d'?valuation, est apparue dans [Babai and Fortnow, 1991].

La philosophie de tout ?a, c'est que la classe P est d?crite par des op?rations, tandis la classe PSPACE l'est par des op?rations et des quantifications (c'est ? dire des op?rateurs d?pendant de l'ensemble des valeurs que les fonctions prennent lorsque varie le uplet de variables quantifi?es). Les quantifications existentielles et universelles sont propres au calcul bool?en ; on fabrique ? partir d'elles des ?nonc?s directement adapt?s ? la description d'une foule de choses, dont le fonctionnement des algorithmes ; leur remont?e en t?te des circuits permet de d?finir la hi?rarchie

polynomiale : c'est une propri?t? qui ressemble ? celle des sommations dans le calcul des polyn?mes. On peut leur pr?f?rer les ?valuations, qui s'appliquent ? un contexte

plus g?n?ral, et qui sont si typiques de PSPACE : en effet, il ne faut pas plus d'espace pour calculer f(0) ou f(l) que pour calculer f(u).

On ne sait pas s?parer P de PSPACE ; la tr?s improbable ?galit? P ? PSPACE

?quivaut, par simple changement de sigle, ? VSPdl(mod 2) = VPdl(mod 2) res treinte aux fonctions num?riques, soit encore bool?ennes. Nous pouvons ?valuer la complexit? d'une fonction bool?enne aussi bien au sens

classique, bool?en, qu'au sens du calcul des polyn?mes, ? la mani?re de Valiant, en

caract?ristique nulle (0 et 1 ?tant alors consid?r?s comme des entiers, et non pas comme des entiers modulo 2). Voici comment ces deux calculs de complexit? se raccordent :

Th?or?me 8. Les fonctions bool?ennes qui sont dans VPdl sont exactement celles

qui sont dans P (version non uniforme). Les fonctions bool?ennes qui sont dans VSPdl sont exactement celles qui sont dans PSPACE (idem).

D?monstration. Si une fonction bool?enne est donn?e par un circuit arithm?

tique, comme on sait que le r?sultat vaut 0 ou 1, il suffit de faire le calcul modulo 2 ;

r?ciproquement, pour simuler des additions et des multiplications modulo 2 par des op?rations portant sur les entiers, restreintes ? {0,1}, il suffit de remplacer les additions par x + y

? 2.x.y.

Si une fonction bool?enne est donn?e par un S-circuit, son calcul modulo 2 donne un S-circuit modulo 2, caract?risant la classe PSPACE. Pour la r?ciproque, on d?finit la classe PSPACE par des circuits comportant des sommes, des produits et des ?valuations modulo deux ; pour les simuler par des op?rations portant sur les entiers, restreintes ? {0,1}, il suffit de remplacer les additions par x + y

? 2.x.y. H

Remarque 6. La m?me d?monstration vaut pour la classe VPt, associ?e ? la

profondeur logarithmique : la partie bool?enne de (c'est-?-dire l'ensemble des fonc tions bool?ennes de) VPt (mod 2) comme celle de VPt est la classe Pt des suites de fonctions bool?ennes calculable en profondeur logarithmique. Par contre, comme la simulation de la somme modulo 2 fait intervenir une multiplication, il est pos sible que la partie bool?enne de VPmd soit un sous-ensemble propre de celle de

VPmd(mod 2). Par ailleurs, comme on ne peut pas simuler directement une som mation modulo 2 par une sommation en caract?ristique nulle, on ne voit pas de raison pour que VNPmd et VNPmd(mod 2) d'une part, VNPdl et VNPdl(mod 2) d'autre part, aient les m?mes parties bool?ennes.



1196 BRUNO poizat

Remarque 7. Si p est un nombre premier quelconque, PSPACE est la partie bool?enne de VSPdl(mod p), P la partie bool?enne de VPdl(mod p), et Pt la

partie bool?enne de VPt(mod p) ; la d?monstration n'est pas aussi directe, car

si p > 3 on ne peut simuler la somme, ni d'ailleurs le produit, modulo p par des

polyn?mes ? coefficients entiers, mais on peut simuler les calculs dans Z /p Z en

repr?sentant les ?l?ments de ce corps par des uplets bool?ens. Cela vient de ce que les classes PSPACE, P et Pt ont des d?finitions solides, ind?pendantes de la base

d'op?rations choisie. Par contre, les autres sont sp?cifiquement li?es ? la somme et au produit, si bien qu'il est possible que les parties bool?ennes de VPmd(mod p), VNPmd (mod p), VNPdl (mod p) varient avec p.

Pour ramener la complexit? des polyn?mes ? celle des fonctions bool?ennes, nous

d?finissons maintenant la fonction-chiffre. Si /(u) est une fonction-num?rique positive, sa fonction-chiffre chf(u, v) donne

le d?veloppement en base deux de l'entier / (u) : chf(u, v) est le N? chiffre, valant 0 ou 1, de f(u), o? N est l'entier dont v est l'?criture en base deux. Autrement dit

f(u) =

Zychf(u,v).iv- =

ZvChf(u,v).T?.l2-vl.1 A (ln~l.vn_{).

Comme nous ne consid?rons que des suites d'entiers au pire doublement ex

ponentielles, leurs fonctions-chiffres ne d?pendent que d'un nombre polynomial d'arguments.

Nous appelons polyn?me-chiffre de / (u) le polyn?me pchf ( u ,z_) = S^chf (u ,v) .zov0

.zn-\vn~l. Comme zv = v.(z

? 1) + 1, ce polyn?me est du premier degr? en

chacune de ses inconnues non-bool?ennes, et f(u) s'obtient en y rempla?ant z, par lf\?.

La fonction-chiffre d'une fonction num?rique quelconque /(u) est constitu?e de la donn?e de la fonction-chiffre de sa valeur absolue, et de sa fonction-signe sgf(w), qui vaut 1 si f(u) > 0, et 0 sinon. La fonction-chiffre d'un polyn?me ? coefficients entiers relatifs est celle sa fonction-coefficient.

Nous attachons ainsi, de mani?re bijective, un objet bool?en ? un polyn?me, mais le passage du polyn?me ? sa fonction-chiffre, ainsi que le passage inverse, pro voquent des augmentations de complexit? qu'il nous faut contr?ler, et qui justifient l'introduction de la classe VSPdl.

Le polyn?me-chiffre d'un polyn?me ? coefficients dans Z s'obtient ? partir de son polyn?me r?duit par remplacement de sa fonction-coefficient par le polyn?me chiffre de cette derni?re ; ses coefficients valent tous 0, 1 ou -1, et il est de degr? un

par rapport ? chacune de ses inconnues. Un polyn?me s'obtient par substitution de

puissances de deux et de variables dans son polyn?me-chiffre. Quand on a affaire ? une fonction-polyn?me, on obtient ainsi une fonction-polyn?me-chiffre !

Nous sommes maintenant arm?s pour montrer ce renforcement du Th?or?me 3 :

Th?or?me 9. La classe VSPdl est stable pour la prise de fonctions-chiffres, soit encore : la suite des fonctions-chiffres d'une suite de polyn?mes de VSPdl est dans

?S?A?B(/poly). D?monstration. Il nous faut reprendre la d?monstration du Th?or?me 3, en

rempla?ant le calcul en nombre des coefficients par leur calcul en chiffres (on ne

peut pas manipuler simultan?ment tous ces chiffres, car il y en a une quantit? expo nentielle !). Comme il faut g?rer un probl?me p?nible de retenues, nous serons moins

pr?cis que lors des d?monstrations des th?or?mes pr?c?dents, en nous contentant




d'indiquer pourquoi les calculs que nous d?crivons se font en espace polynomial : il nous suffit de convaincre notre lecteur qu'il peut les faire sur un petit tableau noir, ? condition de disposer d'un gros stock de craie et de ne pas rechigner ? manipuler souvent le chiffon ; nous lui laissons le soin, s'il le d?sire, de repr?senter ce calcul

par un S-circuit dont il ?valuera la complexit?. Dans un premier temps, nous consid?rons un S-circuit positif C, c'est-?-dire qui

utilise la constante 1 = (-1)2 au lieu de ?1 ? ses entr?es, dont nous notons c la

complexit?. Pour l'expression des fonctions-chiffres, nous consid?rons le polyn?me calcul? en p comme un polyn?me en toutes les variables de C, et pas seulement en celles qui sont libres en p.

Il est facile de calculer la fonction-chiffre d'une entr?e, si bien qu'il ne nous reste

plus qu'? montrer que la fonction-chiffre d'une porte d'op?ration se calcule en

espace polynomial en c ? partir de celle de la porte, ou de celles des deux portes, dont elle re?oit ses fl?ches.

Si p est une porte d'addition, p = p' + p", il faut additionner en chiffres la

fonction-chiffre de p' et celle de p" (autrement dit, ? partir de deux fonctions bool?ennes f(u) et g(u), il nous faut calculer en espace polynomial la fonction chiffre de la somme des deux nombres dont / et g sont les fonctions-chiffres) ; bien que ces fonctions repr?sentent des (uplets de) nombre ? 2e chiffres, ?a se fait en espace polynomial car, si on additionne les nombres par la m?thode de l'?cole

primaire, pour calculer le u? chiffre d'une somme on n'a pas besoin de garder en m?moire tout le calcul qui a ?t? fait auparavant, mais seulement la retenue

qui arrive de la droite (cette addition se repr?sente facilement par un circuit avec

quantifications, car il y a une retenue en u? position si et seulement s'il existe une

position ant?rieure v o? les deux chiffres valent 1, telle que pour chaque position strictement interm?diaire les chiffres ne soient jamais tous les deux 0).

Si p est une porte de sommation, nous pouvons, quitte ? la d?composer, supposer qu'elle ne porte que sur une variable, p = EM// ; nous commen?ons par r?introduire les puissances de u en multipliant la fonction-chiffre de p' par u-, o? v est le uplet de variables repr?sentant le degr? de u ; ensuite, nous effectuons une sommation en chiffre sur (u, v) : nous introduisons c + 1 portes pour calculer le r?sultat ; comme la sommation en chiffres est associative, nous pouvons ?valuer les variables de (u,v) une par une en 0 et en 1, ajouter un petit circuit simulant l'addition de deux nombres de c + 1 chiffres, et passer ? la variable suivante. Nous obtenons ainsi une sorte de fonction-chiffre relativement ? toutes les variables sauf u, si ce n'est que ses pseudo chiffres sont compris entre 0 et 2e + 1, ?tant chacun exprim? par c + 1 chiffres. Comme il y a c + 1 portes pour repr?senter ces chiffres (yo,... ,yn), nous obtenons en fait c + 1 fonctions cho(v)

= yo,... ,chn(v) = yn\ nous effectuons alors des

changements de variables pour d?caler celles de ch? (v) de i pas, afin que que y? soit ? la bonne place. Nous obtenons ainsi ch'0(v),..., ch'n(v), que nous additionnons en chiffres : cette fois, les pseudo-chiffres sont compris entre 0 et c + 1, si bien

qu'? l'?tape suivante on aura au plus log(c + 1) + 1 fonctions. Comme 2m > m si m > 2, on obtient rapidement des chiffres compris entre 0 et 2, que nous traitons comme dans le cas o? p est une porte d'addition : on d?cale les retenues et on additionne les deux fonctions-chiffres. Il ne nous reste plus qu'? r?introduire les variables repr?sentant le degr? de la variable u.



1198 BRUNO POIZAT

Si p est une porte de multiplication, p = p'' .ph', il nous faut effectuer le produit de convolution des fonctions-chiffres de p' et de p". On commence par changer les variables. On est ensuite confront? au probl?me suivant : ?tant donn?es deux fonctions bool?ennes / (u) et g (v), il faut calculer en espace polynomial la fonction chiffre du produit des nombres dont / et g sont les fonctions-chiffres. Pour cela, il faut utiliser un algorithme parall?lis? de multiplication. Multiplier ces deux nombres

par la m?thode de l'?cole primaire revient ? faire un nombre exponentiel d'additions ; on multiplie f(u) par g(v), et on d?cale ces chiffres de v places, ce qui donne une fonction h(u,y_) : il nous faut calculer la fonction-chiffre de la somme des nombres dont la fonction-chiffre est h(u,v), pour un v fix?. Pour parall?liser le

processus, nous faisons des additions d'Ofman (voir [Karatsuba and Ofman, 1963]) qui remplacent, en profondeur constante, quatre nombres donn?s en chiffres par deux nombres de m?me somme ; pour cela, on additionne chiffre par chiffre les trois

premiers modulo deux, puis on calcule un deuxi?me nombre form? des retenues ; on

fait ensuite la m?me chose avec ces deux nombres et le quatri?me (on remarque que les u? chiffres du r?sultat ne d?pendent que des chiffres de rang u, u - 1 et u -1 des

quatre nombres de d?part, ce qui facilite la repr?sentation de cette op?ration par un petit circuit avec changements de variables) ; en effectuant l'addition d'Ofman de h(u,?/,0,0), h(u,v',Q, 1), h(u,vf, 1,0) et de h(u,vf, 1,1), on remplace h(u,v) par une fonction h\ (u, v_x),o? la longueur de v{ est inf?rieure d'une unit? ? celle de

v; apr?s avoir r?p?t? l'op?ration c + 1 fois, il nous reste deux nombres, que nous

additionnons. Quant ? la sommation exprimant le produit de convolution, elle est trait?e comme ci-dessus.

Si le circuit n'est pas positif, on lui associe un circuit positif trois fois plus grand, contenant, pour chaque porte p de C, une porte p+ et une porte p~ telles que le nombre cacul? en p soit la diff?rence du polyn?me calcul? en p+ et du nombre cal cul? en p~ (aux portes d'addition et de sommation on somme les parties positives et les parties n?gatives; si p

= p''.ph', p+

= p'+ .p"+ + p'~.p"~, p~

= p'~.pn+ +

p'+.p"~). Ayant obtenu les fonctions-chiffres des coefficients de la partie positive et de la partie n?gative de la sortie de C, on en d?duit sa fonction-signe en espace poly nomial, en examinant les chiffres un par un ? partir des plus hauts ; on obtient ensuite la fonction-chiffre des valeurs absolues de ses coefficients par une sommation. 3

D'apr?s ce th?or?me, VSPdl est form?e des suites de polyn?mes ? coefficients

entiers, de nombre de variables, degr? et logarithme d'ampleur polynomiaux, et dont la fonction-chiffre est dans PSPACE ; cette classe a ?t? introduite par Koi ran et Perifel dans [Koiran and Perifel, 2007], auquel on pr?f?rera la remarquable r?daction en fran?ais de [Perifel, 2007], sous le nom de VPSPACE (ou plus exac tement VPSPACE?/poly). Comme le montre la suite, son ?tude est grandement facilit?e par sa d?finition en termes de S-circuits.

Remarque 8. Le passage par la fonction-chiffre montre que l'adjonction aux

circuits de portes de changement de variables non-bool?ennes ne fait pas sortir de la classe VSPdl. Remarquons aussi que des ?valuations en a\..... an se ram?nent ? des

?valuations bool?ennes par des changements de variables u^.x + u\.a\3-Yun.an.

Les changements de variables devraient jouer un r?le d?cisif dans toute tentative de d?finition de la complexit? d'espace pour les calculs dans une structure arbitraire introduits par [Goode, 1994] et [Poizat, 1995].




Voici maintenant le pendant du Lemme 6 :

Lemme 10. La classe P est incluse dans VNPmd.

D?monstration. La classe P est caract?ris?e par des circuits de complexit? poly nomiale comportant des portes d'addition et de multiplication modulo deux, qu'on simule respectivement par x + y

? 2.xy et x.y. Pour contr?ler le degr? de la simula

tion, nous utilisons la r?duction parcimonieuse des circuits aux termes. Elle associe au circuit bool?en C(u) un terme bool?en T(w, v) de complexit? un peu plus grande tel que T(u. v) = 0 pour tous les v sauf un si C(u)

= 1, tandis que T(w. v) = 0 pour tous les v si C(u)

= 0 ; autrement dit C(u) = E^T(w. v) : cette sommation modulo

deux se simule par une sommation en caract?ristique 0, puisqu'elle porte sur des va

leurs toutes nulles sauf au plus une, qui vaut 1. Si on parallelise les suites de termes, leur simulation sera dans VPmd, et celle des suites de circuits correspondants dans

VNPmd. H

Corollaire 11. Si P = PSPACE, alors VSPdl = VNPdl ; plus pr?cis?ment, sous cette improbable hypoth?se, toute suite de VSPdl s'obtient ? partir d'une suite de VNPmd par substitution de puissances simplement exponentielles de variables et de 2.

D?monstration. D'apr?s le Lemme 10, si P = PSPACE, le polyn?me-chiffre d'une suite de VSPdl est dans VNPmd. H

Et voici la g?n?ralisation de l'effondrement koiranien du calcul de la factorielle :

Corollaire 12. Si P = PSPACE et VNPmd = VPmd (ou VNPdl = VPdl), alors

VSPdl = VPdl.

D?monstration. Sous ces hypoth?ses, le polyn?me-chiffre d'une suite de VSPdl est dans VPdl. H

L'hypoth?se P = PSPACE est bien s?r tr?s improbable, mais le scandale algo rithmique du mill?naire est qu'on ne sait pas la r?futer. La signification de ces

corollaires, c'est que, si vous croyez, comme il est l?gitime, que VNPdl est une sous classe propre de VSPdl, ou bien que la factorielle n'est pas calculable, vous aurez

beaucoup de mal ? faire passer cette croyance du domaine de la Foi ? celui de la Raison.

R?ciproquement, il est clair que VSPdl = VPdl implique P = PSPACE et VNPdl = VPdl ; mais il n'est pas clair que cette derni?re ?galit? implique VNPmd =

VPmd, car le calcul en degr? born? d'une suite de polyn?mes de sous-degr? born?

peut demander l'emploi de grosses constantes enti?res (un probl?me qui ne se pose pas en caract?ristique p).

On peut aussi se demander s'il est possible de montrer que VNPmd = VPmd im

plique VNPdl = VPdl (on observera que c'est vrai sous l'hypoth?se P = SPACE !). Voici un autre th?or?me, dont la protase est aussi improbable que l'apodose, qui va dans ce sens :

Lemme 13. Si VNPmd = VPmd. toute suite de jonctions bool?ennes qui est dans VNPdl est dans VPmd.

D?monstration. Le calcul d'une fonction bool?enne peut se faire modulo deux, ce qui remplace la sommation par un calcul de parit?. En r?duisant parcimonieuse ment les circuits bool?ens aux termes bool?ens, on obtient, ? partir d'une suite fn



1200 BRUNO POIZAT

de fonctions bool?ennes dans VNPdl, une suite gn de fonctions num?riques dans

VNPmd, telle que la valeur de /? soit le reste modulo deux de l'entier calcul? par g?. Par hypoth?se, gn est dans VPmd ; si dans un circuit arithm?tique calculant gn on

remplace les portes d'additions par des additions modulo 2 de la forme x + y -

2.xy, on calcule /?. En cons?quence /? est dans P, soit encore, d'apr?s le Lemme 10, dans VNPmd - VPmd. H

Ce dernier lemme montre que, sous l'hypoth?se VNPmd = VPmd, la classe P est incluse dans VPmd, classe que [Valiant, Skyumi, Berkowitz, and Rackoff, 1983]

parallelise en profondeur O (log2 ?) tout en pr?servant sa complexit? polynomiale ; si on y ajoute P = PSPACE, on aboutit ? un effondrement s?v?re de PSPACE,

qui, d'apr?s [Koiran and Perifel, 2007], n'a pas ?t? r?fut?, m?me pour des classes d'uniformit? polynomiale.

L'hypoth?se VSPdl = VPdl provoque elle-aussi cet effondrement ; en effet, elle im

plique sa contrepartie modulo 2, qui implique que VNPmd(mod 2) =

VPmd(mod 2), qui implique ? son tour que P est la partie bool?enne

deVPmd(mod2). Lemme 14. Si VNPmd = VPmd, toute suite de polyn?mes de VPdl, de degr?

polynomial et dont les coefficients sont des entiers simplement exponentiels, est dans VPmd.

D?monstration. Gr?ce au calcul des parties homog?nes, la suite /? se calcule

par des petits circuits de petit sous-degr? ; elle est donc calculable par des petits circuits multiplicativement disjoints Cn(xn,an) utilisant des constantes enti?res a_n doublement exponentielles. La fonction-coefficient partielle de Cn(xn, a_n) est dans VNPmd = VPmd ; si les coefficients de /? sont compris entre ? 2m et 2m, on peut remplacer les an par leur reste modulo 22m, et faire les calculs en chiffres pour

qu'ils restent dans cet intervalle, ce qui repr?sente un calcul dans VPdl, m?me si on emploie des algorithmes na?fs pour l'addition et la multiplication en chiffres. Comme il s'agit d'une fonction bool?enne, la fonction-chiffre de la suite /? est dans

VNPt, si bien que /? est dans VNPmd = VPmd. H

Comme aucune m?thode connue ne permet de tronquer les coefficients d'un

polyn?me ? la mani?re de celle utilis?e pour se d?barasser de ses mon?mes de haut

degr?, ni simuler un calcul de polyn?mes modulo p par un calcul en caract?ristique nulle, la conclusion du Lemme 14 semble improbable ; ce lemme indique qu'elle sera

dure ? r?futer.

Lemme 15. Si VSPdl = VPdl et VNPmd = VPmd, toute suite de polyn?mes de

complexit? polynomiale, ? coefficients entiers simplement exponentiels, est calculable

par une suite de circuits de complexit? polynomiale et d'ampleur simplement exponen tielle.

D?monstration. La premi?re hypoth?se met la fonction-chiffre dans VPdl, et la deuxi?me met le polyn?me r?duit dans VPmd. H

Terminons par la mention d'un r?sultat tout r?cent : Peter B?rgisser, dans [B?rgis ser, 2007], am?liore consid?rablement [Koiran, 2004] en pla?ant la Factorielle dans une hi?rarchie qui s'effondre sous la seule hypoth?se VNPmd = VPmd (on remar

quera que ni Koiran, ni B?rgisser ne placent sans hypoth?ses la Factorielle dans




VNPdl). Il ne semble pas d?raisonnable d'esp?rer que la conjonction des m?thodes de Malod et de B?rgisser, ainsi que certains r?sultats de [Perifel, 2007], permettent d'?clairer un jour les rapports entre les classes VNPmd et VNPdl.

R?F?RENCES

[1991] Lazlo Babai and Lance Fortnow, Arithmetization : a new method in structural complexity

theory, Computational Complexity, vol. 1 (1991), pp. 41-66.

[2000] Peter B?rgisser, Completeness and reduction in algebraic complexity theory, Springer Verlag, 2000.

[2007]-, On defining integers in the counting hierarchy and proving lower bounds in algebraic

complexity. Lecture Notes on Computer Science, vol. 4393, 2007.

[1994] John B. Goode, Accessible telephone directories, this Journal, vol. 59 (1994), pp. 92-105.

[1963] Karatsuba and Ofman, Multiplication sur des automates de nombres ? plusieurs chiffres, Soviet

Physics -

Doklady, vol. 7 (1963), pp. 595-596, en russe.

[2004] Pascal Koiran, Valiant's model and the cost of computing integers, Computational Complexity, vol. 13 (2004), pp. 131-146.

[2007] Pascal Koiran and Sylvain Perifel, VPSPACE and a transfer theorem over the Reals, Lecture

Notes on Computer Science, vol. 4393, 2007.

[2003] Guillaume Malod, Polyn?mes et coefficients, th?se de doctorat, Universit? Claude Bernard, 2003.

[2006] Guillaume Malod and N alacha Portier, Characterizing Valiant's algebraic complexity classes, Lecture Notes in Computer Sciences, vol. 4162, 2006, 267-279; version ?tendue ? para?tre au Journal of Complexity.

[1976] David E. Muller and Franco P. Prep?rala, Restructuring of arithmetic expressions for

parallel evaluation, Journal of the Association for Computing Machinery, vol. 23 (1976), pp. 534?543.

[2007] Sylvain Perifel, Probl?mes de d?cision et d'?valuation en complexit? alg?brique, th?se de

doctorat, Universit? de Lyon, 2007.

[1995] Bruno Poizat, Les petits cailloux, Al?as, 1995.

[1979] Leslie G. Valiant, Completeness classes in algebra, Proceedings of the 11th ACM STOC,

ACM, 1979, pp. 249-261.

[1982]-, Reductibility by algebraic projections, L'Enseignement Math?matique, vol. 28 (1982), pp. 253-268, vol. 30, pp. 365-380.

[1983] L. G. Valiant, S. Skyumi, S. Berkowitz, and C. Rackoff, Fast parallel computations using

few processors, SI AM Journal for Computations, vol. 12 (1983), pp. 641-644.

INSTITUT CAMILLE JORDAN

UNIVERSIT? CLAUDE BERNARD

43, BOULEVARD DU 11 NOVEMBRE 1918

69622 VILLEURBANNE CEDEX, FRANCE

E-mail: [email protected]



Documents

A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant