In mathematics, a sum of radicals is defined as a finite

linear combination In mathematics, a linear combination or superposition is an Expression (mathematics), expression constructed from a Set (mathematics), set of terms by multiplying each term by a constant and adding the results (e.g. a linear combination of ''x'' a ...

of th roots: :

\sum_^n k_i\sqrt_i

where

n, r_i

are

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

s and

k_i, x_i

are

real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...

s. A particular special case arising in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

is the

square-root sum problem The square-root sum problem (SRS) is a computational decision problem from the field of numerical analysis, with applications to computational geometry. Definitions SRS is defined as follows:Given positive integers a_1,\ldots,a_k and an intege ...

, asking whether it is possible to determine the sign of a sum of

square root In mathematics, a square root of a number is a number such that y^2 = x; in other words, a number whose ''square'' (the result of multiplying the number by itself, or y \cdot y) is . For example, 4 and −4 are square roots of 16 because 4 ...

s, with integer coefficients, in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

. This is of importance for many problems in computational geometry, since the computation of the

Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of the line segment between them. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, and therefore is o ...

between two points in the general case involves the computation of a

, and therefore the

perimeter A perimeter is the length of a closed boundary that encompasses, surrounds, or outlines either a two-dimensional shape or a one-dimensional line. The perimeter of a circle or an ellipse is called its circumference. Calculating the perimet ...

of a

polygon In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...

or the length of a polygonal chain takes the form of a sum of radicals. In 1991, Blömer proposed a polynomial time

Monte Carlo algorithm In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are the Karger–Stein algorithm and the Monte Carlo algorithm for mini ...

for determining whether a sum of radicals is zero, or more generally whether it represents a rational number.. Blömer's result applies more generally than the square-root sum problem, to sums of radicals that are not necessarily square roots. However, his algorithm does not solve the problem, because it does not determine the sign of a non-zero sum of radicals.

References

{{reflist Computational problems Computer algebra Computational geometry

See also

References