Somme de radicaux

En théorie de la complexité, il existe un problème ouvert de savoir si certaines informations concernant une somme 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. Ce problème algorithmique est important en géométrie algorithmique, puisque le calcul de la distance euclidienne entre deux points dans le cas général implique le calcul d'une racine carrée. Ainsi le périmètre d'un polygone, ou la longueur d'une chaîne polygonale prend la forme d'une somme de radicaux[1].

La somme des radicaux est définie comme une combinaison linéaire finie de radicaux:

${\displaystyle \sum _{i=1}^{n}k_{i}{\sqrt[{r_{i}}]{x_{i}}},}$

où ${\displaystyle n,r_{i}}$ sont des entiers naturels et ${\displaystyle k_{i},x_{i}}$ sont des nombres réels.

La plupart des recherches théoriques sur la géométrie algorithmique du caractère combinatoire prennent le modèle de calcul de la RAM réelle de précision infinie, c'est-à-dire un ordinateur abstrait dans lequel des nombres et des opérations réels sont effectués avec une précision infinie, et la taille d'entrée d'un nombre réel et le coût d'une opération sont constantes[2]^,[3].

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[4]. 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[4].