La somme de radicaux est, en mathématiques, la combinaison linéaire finie de radicaux, qui reste un problème ouvert d'optimisation.
Présentation du problème En théorie de la complexité, savoir si certaines valeurs impliquant des sommes de radicaux peuvent être calculées en temps polynomial en fonction de la taille d'entrée, c'est-à-dire du nombre de bits nécessaires pour représenter cette somme, reste un problème ouvert. Ce problème algorithmique joue un rôle crucial en géométrie algorithmique, puisque le calcul de la distance euclidienne entre deux points implique le calcul d'une racine carrée. Ainsi le périmètre d'un polygone, ou la longueur d'une chaîne polygonale est une somme de radicaux..
La somme des radicaux est définie comme une combinaison linéaire finie de radicaux:
où sont des entiers naturels et sont des nombres réels.
, et la taille d'entrée d'un nombre réel et le coût d'une opération sont constantes...
En particulier, l'intérêt pour la géométrie est le problème de déterminer le signe de la somme des radicaux. Par exemple, la longueur d'un chemin polygonal dans lequel tous les sommets ont des coordonnées entières peut être exprimée en utilisant le théorème de Pythagore comme une somme de racines carrées entières, afin de déterminer si un chemin est plus long ou plus court; Cette expression est une somme de radicaux.
En 1991, Blömer a proposé un algorithme de Monte-Carlo de temps polynomial pour déterminer si une somme de radicaux est nulle, ou plus généralement si elle représente un nombre rationnel. Le résultat de Blömer ne résout pas la complexité informatique de trouver le signe de la somme des radicaux, cela implique que si ce problème est de classe NP, il est aussi en co-NP.
Articles connexes Radical imbriqué Théorème d'Abel
Références
Catégorie:Calcul formel Catégorie:Théorie de la complexité des algorithmes