These - Polynômes et coefficients

Informations

• Publié par: Vofeg
• Nombre de lectures: 53
• Langue: Français

Extrait

N◦d’ordre

: 101-2003

`
THESE

pr´esente´edevant

´
L’UNIVERSITE CLAUDE BERNARD LYON 1

pour l’obtention du
ˆ
DIPLOME DE DOCTORAT

(arreˆte´du30mars1992)

pre´sente´eetsoutenuepubliquementle7juillet2003par
Guillaume Malod

spe´cialite:mathe´matiques
´

Polynoˆmes

Au vu des rapports de

M.PeterB¨urgisser,
M. Felipe Cucker,
M. Christian Michaux.

et

Devant la commission d’examen formee de
´

coefficients

M.GregoryCherlin,pr´esidentdujury,
M. Fokko Du Cloux,
M. Miki Hermann,
M. Pascal Koiran,
M. Christian Michaux,
M.BrunoPoizat,directeurdethe`se.

Remerciements

Jeremercied’abordmondirecteurdethe`seBrunoPoizatpoursesconseilsetsapatience.
J’ai´egalementappr´ecie´lesremarquespre´cisesetd´etaill´eesdesrapporteursFelipeCucker,
Pascal Koiran et Christian Michaux. Je remercie par ailleurs Gregory Cherlin, Fokko Du
ClouxetMikiHermannd’avoiraccepte´departiciperaujury.

Cetravailabe´n´efici´edemesdiscussionsavecHerve´FournieretNatachaPortier.Ila
e´t´ee´labor´edansuneambianced´tenduegraˆceauxoccupantsdubureau219del’institut
e
GirardDesargues:S´ebastienFoulle,OlivierFre´con,CamilleLaurent-Gengoux,Ammar
Mahmood et Boris Thibert.

Amafamilleet`amesamis.

i

Remerciements

Introduction

Tabledesmatie`res

Chapitre1.Calculsetpolynˆomes
ynomes
1. Pol ˆ
2. Calculs
3. Constantes
4.Complexit´e

Chapitre2.Th´eoriedeValiant
1.De´finitions
2. Le permanent
3.Pr´ecisionssurlesconventionsdeValiant
4.Caract´erisationdelaclasseVP
5. Circuits fortement multiplicativement disjoints
6. La classe VQP
7.Classesdecomplexit´epotentielles

Chapitre3.The´oriedeValiantsansconstantes
1.D´efinitions
2.LepolynˆomeHCn
3. Comparaison avec les classes de Valiant

Chapitre4.Coefficientsd’unpolˆasddegr´eborn´e
ynome : c u
1.Positionduproble`me
2. Le corps{01}
3.Polynˆomesdedegre´polynomialementborne
´

Chapitre5.Coefficientsd’unpolynˆome:casdudegre´nonborne´
1. Classes de degre non borne
´ ´
2.Unpolynˆomecomplet
3.Corpsdecaracte´ristiquepositive
4.Conse´quencepourl’hypoth`esedeValiantnonborn´ee
5.Corpsdecaract´eristiquenulle

Chapitre6.D´erivationsimultan´eedepolynoˆmes
1.D´eriv´eepartielleite´re´eparrapporta`unevariable
2.D´erivationpartielleparrapporta`plusieursvariables

Conclusion

Bibliographie

iii

i

1

3
4
4
6
6

9
10
12
14
16
23
31
35

37
38
39
44

47
48
49
50

53
54
55
64
68
68

71
73
76

79

81

Introduction

Aveclesope´rationsusuelles(+−×reutlseemoˆnylopseL.semynˆospolledealcuo,cn)
calculviadesmode`lessimples,commelescircuits,seretrouvent`alabasedesquestions
decomplexit´ealge´brique,lorsqu’onnecalculeplussurlesbool´eensmaisdirectementsur
les´ele´mentsd’uncorps.

Larepr´esentationd’unpolynoˆmeparuncircuitpeuteˆtrebienpluscompactequela
donne´edelalistedescoefficientsdesesmonˆomes,oumˆemedecelledestermesdeson
d´eveloppement.Led´eterminantd’unematricedetaillen, par exemple, est calculable par
un circuit de taille polynomiale enns.entneidlmenooˆemopxeerbmonnuetrompcoisma,
Lesprobl`emesnaturelsquiseposentconcernentl’effetd’ope´rationsmathe´matiquessur
latailledescircuitscalculantdespolynˆomes.Ainsionte´te´e´tudie´slecalculduplusgrand
diviseurcommundedeuxpolynomesetletestd’irre´ducibilit´e.
ˆ

Nousnousinte´ressonsaupassaged’unpolynˆome`asafonctioncoefficientetre´ciproque-
ment,ainsiqu’aucalculdede´riv´eespartiellesite´r´ees.Nousseronsamen´es`autiliserle
cadredelathe´oriedeValiant,quid´efinitunanaloguealge´briquedelaclasseP,laclasse
dessuitesdepolynoˆmesVP,conside´re´escommefacilementcalculables,parmilessuites
depolynoˆmesfacilementdescriptiblesdelaclasseVNP.

Danslepremierchapitrenousdetaillonslecadredenotre´etude,enpre´cisantlesmode`les
´
decalculemploye´setlesnotionsdecomplexite´misesenjeu.

Nouspr´esentonsbri`evementaudeuxie`mechapitrelathe´oriedeValiantclassique.Nous
introduisons alors la notion de circuit multiplicativement disjoint afin de donner une nou-
vellecaracte´risationdelaclasseVP(proposition1).Nousillustronscettecaracte´risation
endonnantunepreuvesimplifi´del’e´galite´entrelesclassesVNPetVNPeet nous
ee
´etudionsquelques-unesdesperspectivesquecettenotionengendre.Enparticulier,ladis-
jonctiondesmultiplicationss’appliqueaussia`laclasseVQPdessuitesdepolynˆomesde
complexit´equasi-polynomialementborn´ee.Nousende´duisonsunepreuvesimpledela
VQP-compl´etudedude´terminantetr´epondons`auneconjecturedeBu¨rgisserendonnant
d’autrespolynoˆmesVQP-complets(th´eor`eme5etcorollaire2).

Letroisi`emechapitreestconsacr´ea`l’expose´d’uneversionplusstrictedelath´eoriede
Valiant,o`ul’onnes’autorisepasdeconstantesarbitrairesetquenousutiliseronsafin
debienmettreenvaleurlescalculsne´cessairespourpasserd’unpolynoˆmea`safonction
coefficient.Nousde´montronslesr´esultatsessentielsdanscecadre,enprofitantdutravail

1

2

INTRODUCTION

effectu´eauchapitrepre´ce´dent,notammentlacompl´etudeduhamiltonien,quenouschoi-
sissonsdepre´f´erenceaupermanentafinquelesproprie´t´esd´emontre´essoientvalablesen
toutecaracte´ristique.

Lequatrie`mechapitreabordeenfinlesquestionsquinouspre´occupent.Nousposonsle
proble`meetmontronsquelecadredelath´eoriedeValiantstricteetletravaileffectue
´
autroisie`mechapitrepermettentd’obtenirrapidementdesr´esultatspourlespolynˆomes
dedegr´epolynomialementborn´e:d’unepartquelaclasseVNP0est stable par passage
`lafotioncoefficientetre´ciproquement(proposition2),d’autrepartquesupposer
a nc
quecere´sultatestvraipourlaclasseVP0uqe´lavitserqmeVPuet`enffiraa0= VNP0
(th´eor`eme8).

Noustentonsaucinqui`emechapitred’e´tendreces´ltatsaucasdespolynˆomesde
resu
degr´enonborn´e.Nousmontrons,enadoptantunede´marchesimilaireaucasborne´,que
leprobl`emeestessentiellementceluiducalculrapidedegroscoefficientsbinomiaux.Deux
cassepresententalors:surlescorpsdecaract´eristiquepositivenousparvenonsa`calculer
´
rapidementetobtenonsdesr´esultatssimilairesa`ceuxduquatrie`mechapitre(propo-
sition5etthe´ore`me10),ainsiqu’unr´esultatinte´ressantsurlesrapportsentreclasses
dedegre´borne´etnon-borne´(th´eor`eme11);surlescorpsdecaracte´ristiquenulle,nous
constatonsqueleprobl`emerevientalorsexactementa`calculerrapidementcesgroscoef-
ficientsbinomiaux,etquecelaauraitpourcons´equenceuncalculrapidedelafactorielle.

Enfindanslesixie`mechapitrenous´etudionsl’effetdelad´erivationsurlescircuitscalculant
despolynˆomes.Nousmontronsd’abordqueceprobl`emeestlie´auxquestionssoulev´ees
auparavant(propositions6et7).L’actionded´eriv´eespartiellesite´r´eespeutfaireexploser
latailledelarepr´esentationdepolynˆomespardescircuits.Nousretrouvonsler´esultat
deKaltofenquimontrequec’estlenombredevariablesparrapportauxquellesond´erive
quiauneffetn´efaste,plusquel’ordredede´rivation,etnousmontronsqu’ilnecoˆutepas
beaucouppluscheralorsdecalculersimultan´ementtouteslesd´erive´espartiellesjusqu’`a
unordredonne´(th´ore`me15).
e

CHAPITRE 1

Calculsetpolynoˆmes

3

4

ˆ
1. CALCULS ET POLYNOMES

Nouspre´sentonsdanscecourtchapitrecequenousvoulonscalculer,ainsiquelesmode`les
decalculetlesmesuresdecomplexite´employe´esparlasuite.

1.Polynˆomes

Nousnousint´eressonsauxpolynoˆmesa`coefficientsentiersencaracte´ristiquefix´ee.Ces
polynˆomessontdoncdespolynoˆmesabstraits,donn´esparlasuitedescoefficientsdeleurs
monˆomes.Encaracte´ristiquenulle,deuxpolynˆomessontidentiquessilesdeuxsuites
sont´egales.Encaracte´ristiquepositivepesdeuxiquessilnoitedtnnyoˆemssolxpeu,d
suitessonte´galesmodulop. Il importe de distinguer cette notion de c