×

A computer science approach to diophantine approximation. (Une approche informatique pour l’approximation diophantienne.) (French. Abridged English version) Zbl 0814.14050

Cette note présente une nouvelle méthode, basée sur les calculs d’évaluation de la théorie de la complexité, pour établir une version effective du théorème des zéros de Hilbert. La méthode s’étend à des problèmes de division plus généraux. L’idée est de remplacer un polynôme par un algorithme (arborescent) permettant d’en calculer les valeurs. La complexité est mesurée par le nombre de nœuds, la profondeur et les niveaux de l’algorithme (ces dernières quantités contrôlent le nombre d’opérations élémentaires intervenant à chaque nœud). Cette approche est intéressante en ce qu’elle permet une analyse plus détaillée que par la simple notion de degré (et de hauteur dans les cas arithmétiques) de la complexité d’un polynôme, mais elle ne fournit jusqu’à présent que des constantes inexplicites.

MSC:

14Q20 Effectivity, complexity and computational aspects of algebraic geometry
11Y16 Number-theoretic algorithms; complexity
68Q25 Analysis of algorithms and problem complexity
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
PDFBibTeX XMLCite