Complexité en temps polynomial : calcul d’une réduite de Hermite, les différentes représentations des nombres réels

Abstract

Première partie : les différentes représentations des nombres réels Nous étudions différentes manières de présenter les nombres réels. Nous comparons ces présentations du point de vue des fonctionnelles récursives d’une part, et de celui des classes de complexité d’autre part. L’impossibilité d’obtenir certaines fonctions sous forme de fonctionnelles récursives est en général facile à établir. Cette impossibilité peut souvent être explicitée (et renforcée) en termes de complexité : - Il existe une suite de faible complexité dont l’image est une suite non récursive. - Il existe des objets de faible complexité mais dont les images sont des objets de complexité arbitrairement grande. (Le plus souvent la « faible complexité » est celle en temps linéaire ou polynomial) En outre, certaines présentations des réels équivalentes du point de vue des fonctionnelles récursives se distinguent nettement du point de vue de la complexité. Nous faisons une étude particulière concernant les développements en fraction continue (dfc). Nous précisons exactement quelle est la partie de l’information disponible dans le dfc d’un réel x qui équivaut à l’information disponible dans sa coupure de Dedekind. Nous avons montré également que la somme de 2 réels dont le dfc est calculable en temps polynomial peut être un réel dont le dfc est de complexité arbitrairement grande. Ce travail confirme que seule une présentation des réels via des suites de rationnels explicitement de Gauchy est adaptée aux calculs avec des réels. Deuxième partie : Complexité du calcul d’une réduite de Hermite. Nous nous intéressons ici à la complexité du calcul d’une réduite de Hermite d’une matrice à entrées dans un anneau K[X] lorsque K est un corps dans lequel le calcul des déterminants est dans la classe. Nous proposons une méthode de sous-résultants généralisés, c.à.d. relevant purement de l’algèbre linéaire en dimension finie (bien contrôlée) sur le corps des coefficients. Au fond, on a remplacé un algorithme récursif dans K[X] par un calcul d’algèbre linéaire sur K.