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. The problem was posed in 1981, and likely earlier. SRS is defined as follows: :Given positive integers a_1,\ldots,a_k and an integer t, decide whether \sum_{i=1}^k \sqrt{a_i} \leq t . An alternative definition is: :Given positive integers a_1,\ldots,a_k and b_1,\ldots,b_k , decide whether \sum_{i=1}^k \sqrt{a_i} \leq \sum_{i=1}^k \sqrt{b_i} .

The square-root sum problem (SRS) is a computational decision problem from the field of numerical analysis, with applications to computational geometry. The problem was posed in 1981, and likely earlier. SRS is defined as follows: Given positive integers a_1,\ldots,a_k and an integer t, decide whether \sum_{i=1}^k \sqrt{a_i} \leq t . An alternative definition is: Given positive integers a_1,\ldots,a_k and b_1,\ldots,b_k , decide whether \sum_{i=1}^k \sqrt{a_i} \leq \sum_{i=1}^k \sqrt{b_i} . One way to solve SRS is to prove a lower bound on the absolute difference \left|t - \sum_{i=1}^k \sqrt{a_i} \right| or \left|\sum_{i=1}^k \sqrt{a_i} - \sum_{i=1}^k \sqrt{b_i}\right| . 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 \sum_{i=1}^k \sqrt{a_i} - \sum_{i=1}^k \sqrt{b_i} , where a i and b i 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. 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 prove by an explicit construction that, for any k and n, r(n,k)\in O(n^{-2k+3/2}) , so R(n,k)\geq (2k-3/2)\cdot \log{n} . This number is optimal for k=2, and also for a wide range of integers. Burnikel, Fleischer, Mehlhorn and Schirra proved an upper bound on the number of digits: R(n,k)\in O(2^{2 k}\cdot \log{n}) . Cheng, Meng, Sun and Chen showed that R(n,k)\in 2^{O(n/\log{n})}\cdot \log{n} . Cheng and Li showed that R(n,k)\in 2^{O(n/\log{n})} . This implies an that SRS can be solved in time 2^{o(k)} \cdot (\log{n})^{O(1)} , as long as n is in o(k log k). They also present an algorithm to compute r(n,k) in time n^{k+o(k)} . Eisenbrand, Haeberle and Singer prove that r(n,k)\geq \gamma\cdot k^{-4k} , where gamma is a constant that depends on the inputs a 1 ,...,a k , and steps from the Subspace theorem. This improves the previous bound r(n,k)\geq \left( 2k\cdot \sqrt{n}\right)^{-4^k} . , and additional linear constraints x_i\geq 0, \sum_{i=1}^n x_i \geq k . The resulting SDP is feasible if and only if SRS is feasible. As the runtime complexity of SRS in the Turing machine model is open, the same is true for SDP feasibility (as of 1997).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371866449 under CC BY-SA 4.0; modifications have been made.