Square-root sum problem
It has been suggested that this article be merged into Sum of radicals. (Discuss) Proposed since January 2024. |
What is the Turing run-time complexity of 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:[1]
Given positive integers and an integer t, decide whether .
An alternative definition is:
Given positive integers and , decide whether .
Run-time complexity
SRS can be solved in polynomial time in the Real RAM model.[2] However, its run-time complexity in the Turing machine model is open, as of 1997.[1] The main difficulty is that, in order to solve the problem, the square-roots should be computed to a high accuracy, which may require a large number of bits. The problem is mentioned in the Open Problems Garden.[3]
Blomer[4] presents a polynomial-time Monte Carlo algorithm for deciding whether a sum of square roots equals 0.
Allender, Burgisser, Pedersen and Miltersen[5] prove that SRS lies in the counting hierarchy (which is contained in PSPACE).
Separation bounds
One way to solve SRS is to prove a lower bound on the absolute difference or . Such lower bound is called a "separation bound" since it separates between the difference and 0. For example, if the absolute difference is at least 2-d, it means that we can round all numbers to d bits of accuracy, and solve SRS in time polynomial in d.
This leads to the mathematical problem of proving bounds on this difference. Define r(n,k) as the smallest positive value of the difference , where ai and bi are integers between 1 and n; define R(n,k) is defined as -log r(n,k), which is the number of accuracy digits required to solve SRS. Computing r(n,k) is open problem 33 in the open problem project.[6]
In particular, it is interesting whether r(n,k) is in O(poly(k,log(n)). A positive answer would imply that SRS can be solved in polynomial time in the Turing Machine model. Some currently known bounds are:
- Qian and Wang[7] prove by an explicit construction that, for any k and n, , so . This number is optimal for k=2, and also for a wide range of integers.
- Burnikel, Fleischer, Mehlhorn and Schirra[8] proved an upper bound on the number of digits: .
- Cheng, Meng, Sun and Chen[9] showed that .
- Cheng and Li[10] showed that . This implies an that SRS can be solved in time , as long as n is in o(k log k). They also present an algorithm to compute r(n,k) in time .
- Eisenbrand, Haeberle and Singer[11] prove that , where gamma is a constant that depends on the inputs a1,...,an, and steps from the Subspace theorem. This improves the previous bound .
Applications
SRS is important in
Etessami and Yannakakis
Relation to semidefinite programming
SRS also has a theoretic importance, as it is a simple special case of a semidefinite programming feasibility problem. Consider the matrix . This matrix is
Extensions
Kayal and Saha
References
- ^ S2CID 17221714.
- ISSN 0885-064X.
- ^ "Complexity of square-root sum | Open Problem Garden". garden.irmacs.sfu.ca. Retrieved 2024-01-01.
- ^ "CSDL | IEEE Computer Society". www.computer.org. Retrieved 2024-01-01.
- ISSN 0097-5397.
- ^ Demaine, Erik D. "TOPP: Problem 33: Sum of Square Roots". topp.openproblem.net. Retrieved 2024-01-01.
- ISSN 0020-0190.
- S2CID 34502818.
- ISSN 0025-5718.
- ISSN 0304-3975.
- arXiv:2312.02057 [cs.CG].
- ISSN 1860-5974.
- S2CID 7225729.
This article needs additional or more specific categories. (January 2024) |