Somme de radicaux

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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:

où  sont des entiers naturels et  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].

Articles connexes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) Wolfgang Mulzer et Günter Rote, « Minimum-Weight Triangulation Is NP-Hard », Journal of the ACMM (en), série Proceedings of the 22nd Annual Symposium on Computational Geometry (en), Sedona, 5-7 juin 2006, vol. 55, no 2,‎ .
  2. (en) Franco P. Preparata et Michael Ian Shamos, Computational Geometry : An Introduction, New York, Springer, coll. « Texts and monographs in computer science », , 6e éd. (1re éd. 1985) (ISBN 3-540-96131-3).
  3. (en) Johannes Grabmeier, Erich Kaltofen et Volker Weispfenning, Computer Algebra Handbook, New York, Springer, (ISBN 9783540654667).
  4. a et b Johannes Blömer, « Computing sums of radicals in polynomial time », dans Proceedings 32nd Annual Symposium on Foundations of Computer Science, (DOI 10.1109/SFCS.1991.185434), p. 670