Portier
Le Jeudi 13 Janvier 2000 à 14h30
(ENS Lyon)
Algorithmique dans les corps et dans les corps différentiels : des
problèmes difficiles
Résumé/Abstract :
On doit à L. Blum, M. Shub et S. Smale un modèle de calcul sur
les corps. Il permet de définir les classes de complexité dans
un cadre plus général que le cas classique avec les mots
booléens. On peut alors en particulier se poser la question ``P=NP ?''
sur un corps et étudier ses liens avec la même question dans
le cas classique.
B. Poizat propose un modèle de calcul qui utilise les circuits, qui
est équivalent au précédent dans le cas des corps mais
qui permet de définir des classes de complexité sur une
structure quelconque. Je m'intéresse au cas des corps
différentiels.
Je commencerai par rappeler quelques théorèmes de transfert sur
la question ``P=NP ?'' dans les corps et les corps différentiels.
Puis je me poserai la question de savoir quelle est la puissance algorithmique
de la dérivée.