Is there an polynomial time algorithm to find that sum of square-roots is less than an integer?

Given: A list of $n$ integers $x_1,x_2,\dots,x_n$ and an integer $k$.

Determine: Is $\sqrt x_1 + \sqrt x_2 \cdots \sqrt x_n \le k$?

Question: Is there any polynomial time algorithm for the above problem? If yes, give an algorithm; otherwise prove it.

The complexity of the square-root sum problem is a long-standing open question. The stumbling block is that, although we know how to compute square roots efficiently, we don't know if it's possible to determine whether $\sum_i \sqrt{x_i}\leq k$ by evaluating only a polynomial number of bits of each square root.

The specific problem with the algorithm you propose in the question is that the phrase "compute the square root of each value" is underspecified. Any irrational square root (e.g., $\sqrt{2}$) requires computing an infinite number of bits, so you need to state what precision you're using.

StackExchange Computer Science Q#84800, answer score: 21