Sum of radicals
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.[1]
The sum of radicals is defined as a finite linear combination of radicals:
![{\displaystyle \sum _{i=1}^{n}k_{i}{\sqrt[{r_{i}}]{x_{i}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88f8e5154b52c32759c00bcfd8940b97ad925b4f)
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.[2] 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.[3]
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.[4] 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.[4]
See also
References
- ^ Mulzer, Wolfgang; Rote, Günter (2008). "Minimum-weight triangulation is NP-hard". Journal of the ACM. 55 (2): A11:1–A11:29. arXiv:cs/0601002. doi:10.1145/1346330.1346336. MR 2417038.
- ^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. ISBN 978-0-387-96131-6. 1st edition: 2nd printing, corrected and expanded, 1988: ; Russian translation, 1989.
- ^ Computer Algebra Handbook, 2003, ISBN 3-540-65466-6
- ^ a b Blömer, Johannes (1991). "Computing sums of radicals in polynomial time". [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. pp. 670–677. doi:10.1109/SFCS.1991.185434. ISBN 978-0-8186-2445-2..