Vincent BLONDEL
charg\u00e9 de cours \u00e0 l’Universit\u00e9 de Li\u00e8ge, examinateur
Fokko du CLOUX
professeur \u00e0 l’Universit\u00e9 Claude Bernard de Lyon, examinateur
Fran\u00e7oise DELON
directrice de recherches au CNRS \u00e0 Paris VII, pr\u00e9sidente du jury
Christian MICHAUX
chef de travaux \u00e0 l’Universit\u00e9 de Mons, rapporteur
Bruno POIZAT
professeur \u00e0 l’Universit\u00e9 Claude Bernard de Lyon, directeur de th\u00e8se<\/p>\n\n\n\n
Felipe CUCKER, professeur \u00e0 l’Universitat Pompeu Fabra de Barcelone,
Christian MICHAUX, chef de travaux \u00e0 l’Universit\u00e9 de Mons.<\/p>\n\n\n\n
La premi\u00e8re partie est consacr\u00e9e \u00e0 l’\u00e9tude de la complexit\u00e9 alg\u00e9brique des corps diff\u00e9rentiels de caract\u00e9ristique nulle. Nous pouvons d\u00e9finir les classes P et NP sur un corps diff\u00e9rentiel K (cf le livre \u00ab\u00a0Les petits cailloux\u00a0\u00bb de Bruno Poizat) . En utilisant le th\u00e9or\u00e8me des t\u00e9moins de L. Blum, M. Shub et S. Smale, nous montrons la P-stabilit\u00e9 de la th\u00e9orie des corps diff\u00e9rentiels de caract\u00e9ristique nulle : la restriction d’un probl\u00e8me P sur un corps diff\u00e9rentiel K \u00e0 un sous corps k de K est encore P. Nous en d\u00e9duisons que la question P=NP? a la m\u00eame r\u00e9ponse dans tous les corps diff\u00e9rentiellement clos de caract\u00e9ristique nulle. Nous montrons ensuite que la d\u00e9riv\u00e9e ne nous permet pas de calculer plus vite les grandes racines et les grandes puissances d’un \u00e9l\u00e9ment.
La deuxi\u00e8me partie est une g\u00e9n\u00e9ralisation de l’article de Manindra Agrawal et Somenath Biswas : \u00ab\u00a0Universal Relations\u00a0\u00bb. Les auteurs d\u00e9finissent pour le cas des calculs au sens ordinaire, une notion plus forte que la NP-compl\u00e9tude. Par d\u00e9finition, \u00e0 chaque probl\u00e8me NP-complet X est associ\u00e9 un probl\u00e8me Y, que nous appelons r\u00e9solution associ\u00e9e \u00e0 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\u00e9 solution de x pour X. Si toute r\u00e9solution R se r\u00e9duit \u00e0 Y, de mani\u00e8re \u00e0 ce que les solutions pour R se d\u00e9duisent des solutions pour Y, Y sera appel\u00e9e r\u00e9solution universelle. Les auteurs montrent ensuite un th\u00e9or\u00e8me qui permet de prouver qu’une r\u00e9solution est universelle. Nous g\u00e9n\u00e9ralisons cette d\u00e9finition et ce th\u00e9or\u00e8me aux calculs effectu\u00e9s dans une structure arbitraire, en particulier aux calculs sur les r\u00e9els d\u00e9finis dans l’article \u00ab\u00a0On a theory of computation and complexity over the real numbers : NP-completeness, recursive functions and universal machines\u00a0\u00bb de L. Blum, M. Shub et S. Smale, puis nous \u00e9tudions des exemples.<\/p>\n","protected":false},"excerpt":{"rendered":"
pr\u00e9sent\u00e9e devant l’UNIVERSIT\u00c9 CLAUDE BERNARD – LYON Ipour obtenir le titre de DOCTEURE EN SCIENCESdans la sp\u00e9cialit\u00e9 MATH\u00c9MATIQUESparNatacha PORTIER Complexit\u00e9 alg\u00e9briqueStabilit\u00e9 polynomiale des corps diff\u00e9rentiels&R\u00e9solutions universelles pour des probl\u00e8mes NP-complets soutenue le mercredi 9 d\u00e9cembre 1998 Jury : Vincent BLONDELcharg\u00e9 de cours \u00e0 l’Universit\u00e9 de Li\u00e8ge, examinateurFokko du CLOUXprofesseur \u00e0 l’Universit\u00e9 Claude Bernard de Lyon, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-103","post","type-post","status-publish","format-standard","hentry","category-non-classe"],"_links":{"self":[{"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/posts\/103","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/comments?post=103"}],"version-history":[{"count":1,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/posts\/103\/revisions"}],"predecessor-version":[{"id":104,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/posts\/103\/revisions\/104"}],"wp:attachment":[{"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/media?parent=103"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/categories?post=103"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/tags?post=103"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}