| dbo:abstract
|
- 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. 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. 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. (fr)
- In computational complexity theory, there is an open problem of whether some information about a sum of radicals may be computed in polynomial time depending on the input size, i.e., in the number of bits necessary to represent this sum. It is of importance for many problems in computational geometry, since the computation of the Euclidean distance between two points in the general case involves the computation of a square root, and therefore the perimeter of a polygon or the length of a polygonal chain takes the form of a sum of radicals. The sum of radicals is defined as a finite linear combination of radicals: where are natural numbers and are real numbers. Most theoretical research in computational geometry of combinatorial character assumes the computational model of infinite precision real RAM, i.e., an abstract computer in which real numbers and operations on them are performed with infinite precision and the input size of a real number and the cost of an elementary operation are constants. However, there is research in computational complexity, especially in computer algebra, where the input size of a number is the number of bits necessary for its representation. Of particular interest in computational geometry is the problem of determining the sign of the sum of radicals. For instance, the length of a polygonal path in which all vertices have integer coordinates may be expressed using the Pythagorean theorem as a sum of integer square roots, so in order to determine whether one path is longer or shorter than another in a Euclidean shortest path problem, it is necessary to determine the sign of an expression in which the first path's length is subtracted from the second; this expression is a sum of radicals. In a similar way, the sum of radicals problem is inherent in the problem of minimum-weight triangulation in the Euclidean metric. In 1991, Blömer proposed a polynomial time Monte Carlo algorithm for determining whether a sum of radicals is zero, or more generally whether it represents a rational number. While Blömer's result does not resolve the computational complexity of finding the sign of the sum of radicals, it does imply that if the latter problem is in class NP, then it is also in co-NP. (en)
|
| rdfs:comment
|
- In computational complexity theory, there is an open problem of whether some information about a sum of radicals may be computed in polynomial time depending on the input size, i.e., in the number of bits necessary to represent this sum. It is of importance for many problems in computational geometry, since the computation of the Euclidean distance between two points in the general case involves the computation of a square root, and therefore the perimeter of a polygon or the length of a polygonal chain takes the form of a sum of radicals. where are natural numbers and are real numbers. (en)
- 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. (fr)
|
