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.
In case David's answer is not clear: Let's say you have 10,000 integers $x_i$ and k = 1,000,000. You can easily add the square roots of n integers using floating-point operations in $O(n)$. And if the result is say 999,999.537 or 1,000,000.214 then you have the answer. If the result is close to 1,000,000 then you can do a very careful analysis of floating-point rounding errors, and if the sum is say 999,999.999999999 then you probably get your answer. If the sum is too close to k, then you can do arithmetic with higher precision. So there will be a constant c, depending on the exact implementation, so you can find the correct answer in $cn$ time for the huge majority of all cases (if n is truly large then it will take a bit longer because the numbers involved just get huge, but then the time will be longer than your lifetime anyway).
The problem is that there are sums of square roots that can get very, very close to k. For example, you can define f(x) = number of choices for $x_i$ such that the sum of the square roots is ≤ x, then you expect 2f'(k) * eps choices of $x_i$ so the sum of square roots is within eps away from k. You expect one combination where the sum of square roots is within eps away from k if eps ≥ 1 / 2f'(k). You can calculate an estimate of this eps, figure out what precision your calculations would need to get the right answer, and how long it would take you to get the result with this precision. This might or might not be polynomial, depending on how small eps is.
But it is worse: What I said above is how close you expect a sum to be to k. But it might be a lot closer by coincidence. It would be very, very hard to prove that it cannot get an awful lot closer. So it might be the case that you find the answer in linear time in most cases (> 99.9999999999%), that you expect to find the answer in polynomial time in all cases (or not), but in any case you cannot (easily) prove this, and nobody has done so yet.
It might be that you could answer the question without calculating the sum, but according to what David says, nobody has shown a way to do that in polynomial time either.
If anyone has done a calculation how close we expect sums of square roots to come close to any integers, I'd be happy to know. BTW. I think the sum of square roots of integers is only equal to an integer if all square roots are integers, so that is easily excluded.
PS. A rough estimate: Let's say we add 10,000 square roots of integers, each less than 1,000,000. That's square roots of $10^{12}$ integers, and since their order is not relevant, there are about $(10^{12})^{10,000} / 10,000!$ sums. That's more than $10^{80,000}$ sums. So we expect one of these sums to be within $10^{-80,000}$ distance to an integer, requiring calculations with more than 80,000 digits precision.
PS. Given integers a, b, c, d, k, and using IEEE 754 double precision arithmetic, the first case where sqrt(a)+sqrt(b)+sqrt(c)+sqrt(d) < k gives a different result from the mathematically correct one is for a, b, c, d = 4640, 5397, 3001, 3322 and k = 254. In this case, the sum is calculated as exactly 254, when the mathematical result is less than 254. Obviously when the floating-point result equals the integer, we cannot know whether it was rounded up or down, so in this case the result should never have been trusted.
With a, b, c, d = 6222, 8801, 14431, 8132 and k = 383, the calculated sum is greater than k, while the mathematical result is less. The order of the numbers doesn't matter except that 14431 must be the third number.
If we change the order of operations by adding (sqrt(a)+sqrt(b)) + (sqrt(c)+sqrt(d)) (note the added parentheses), which will change the rounding errors and tend to decrease them, then a, b, c, d = 12558, 407, 16501, 18308 and k = 396 is the first case where the calculated sum is greater than k, while the mathematical result is less.
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.
