présentée devant l’UNIVERSITÉ CLAUDE BERNARD – LYON I
pour obtenir le titre de DOCTEURE EN SCIENCES
dans la spécialité MATHÉMATIQUES
par
Natacha PORTIER
Complexité algébrique
Stabilité polynomiale des corps différentiels
&
Résolutions universelles pour des problèmes NP-complets
soutenue le mercredi 9 décembre 1998
Jury :
Vincent BLONDEL
chargé de cours à l’Université de Liège, examinateur
Fokko du CLOUX
professeur à l’Université Claude Bernard de Lyon, examinateur
Françoise DELON
directrice de recherches au CNRS à Paris VII, présidente du jury
Christian MICHAUX
chef de travaux à l’Université de Mons, rapporteur
Bruno POIZAT
professeur à l’Université Claude Bernard de Lyon, directeur de thèse
Rapporteurs :
Felipe CUCKER, professeur à l’Universitat Pompeu Fabra de Barcelone,
Christian MICHAUX, chef de travaux à l’Université de Mons.
Résumé :
La première partie est consacrée à l’étude de la complexité algébrique des corps différentiels de caractéristique nulle. Nous pouvons définir les classes P et NP sur un corps différentiel K (cf le livre « Les petits cailloux » de Bruno Poizat) . En utilisant le théorème des témoins de L. Blum, M. Shub et S. Smale, nous montrons la P-stabilité de la théorie des corps différentiels de caractéristique nulle : la restriction d’un problème P sur un corps différentiel K à un sous corps k de K est encore P. Nous en déduisons que la question P=NP? a la même réponse dans tous les corps différentiellement clos de caractéristique nulle. Nous montrons ensuite que la dérivée ne nous permet pas de calculer plus vite les grandes racines et les grandes puissances d’un élément.
La deuxième partie est une généralisation de l’article de Manindra Agrawal et Somenath Biswas : « Universal Relations ». Les auteurs définissent pour le cas des calculs au sens ordinaire, une notion plus forte que la NP-complétude. Par définition, à chaque problème NP-complet X est associé un problème Y, que nous appelons résolution associée à X, qui est P, et tel que x soit dans X si et seulement s’il existe y, de longueur polynomiale en elle de x, tel que (x,y) soit dans Y. Un tel y est appelé solution de x pour X. Si toute résolution R se réduit à Y, de manière à ce que les solutions pour R se déduisent des solutions pour Y, Y sera appelée résolution universelle. Les auteurs montrent ensuite un théorème qui permet de prouver qu’une résolution est universelle. Nous généralisons cette définition et ce théorème aux calculs effectués dans une structure arbitraire, en particulier aux calculs sur les réels définis dans l’article « On a theory of computation and complexity over the real numbers : NP-completeness, recursive functions and universal machines » de L. Blum, M. Shub et S. Smale, puis nous étudions des exemples.