Le problème des grandes puissances et celui des grandes racines.
Résumé
Soit f une fonction de N dans N qui ne soit pas
calculable en temps polynomial, et a un élément d'un corps
différentiel K de caractéristique nulle. Nous appelons problème des
grandes puissances l'ensemble des uples x= (x_1, ..., x_n) de
K tels que
x_1=a^{f(n)}, et problème des grandes racines l'ensemble des uples
x de K tels que x_1^{f(n)}=a. Ce sont deux exemples de
problèmes que l'utilisation de la dérivée ne permet pas de résoudre
plus rapidement. Nous montrons que le problème des grandes racines
n'est pas polynomial au sens des corps différentiels, même si nous
autorisons un nombre polynomial de paramètres, et que le problème des
grandes puissances n'est pas polynomial au sens des corps
différentiels, même au niveau non uniforme. Les démonstrations utilisent la
stabilité polynomiale de la théorie des corps de caractéristique
nulle, montrée par L. Blum, F. Cucker, M. Shub et S. Smale, ainsi que lemme de
réduction qui permet de ramener un polynôme
différentiel des variables x à un polynôme des variables
x et de leurs dérivées.
Abstract
Let f be a function from N to N that can not be computed
in polynomial time, and let a be an element of a differential field
K of characteristic 0. The problem of large powers is the set of
tuples x= (x_1, ..., x_n) of K so that x_1=a^{f(n)}, and
the problem of large roots is the set of tuples x of K so that
x_1^{f(n)}=a. These are two examples of problems that the use of
derivation does not allow to solve quicker. We show that the problem
of high roots is not polynomial for the differential field K, even if
we use a polynomial number of parameters, and that the problem of large
powers is not polynomial for the differential field K, even for
non-uniform complexity. The proofs use the polynomial stability
(i.e. the elimination of parameters) of field of characteristic 0,
shown by L. Blum, F. Cucker, M. Shub and S. Smale, and the reduction
lemma, that
transforms a differential polynomial in variables x into a
polynomial in variables x and their derivatives.