Here is my attempt at proving that this can be done in P-time. I am using the fact that square roots can be expressed as periodic continued fractions, and that there is an upper bound on the period of these fractions which must thus be unique. Please tell me if there are any issues! I hope this holds :)
The period of the square root of n is less than k1 * (sqrt(n) log (log (log (n))) ) = Lm(n)
We can find this period in polynomial time (n^3)
each term is smaller than 2*sqrt(n)
Therefore, all square roots up to n are uniquely represented as part of a continued fraction expansion as a0 + 1/(a1 + 1/ (a2 + ...)) ... up to a[Lm(n)].
If we transform this nested fraction into a decimal number, any modification of this fraction will necessarily lead to a delta in the number by at least (a[Lm(n))]^-(Lm(n)), which is at most 2sqrt(n)^-(sqrt(n)
Therefore, accurately computing the square root up to the most significant digit of 2sqrt(n)^-(2sqrt(n)) will yield a result distinct from any square root up to n.
In the case of a sum of square roots, assuming that n is the largest root, accurately computing the sum up past the most significant digit of 2sqrt(n)^-Lm(n) will be sufficient
to decide if a sum of square roots is larger than or smaller than another.
2sqrt(n)^-Lm(n) is reciprocally subexponential, thus the number of digits needing to be computed will grow sub-linearly with n
Therefore, the problem can be solved in polynomial time.
The period of the square root of n is less than k1 * (sqrt(n) log (log (log (n))) ) = Lm(n) We can find this period in polynomial time (n^3) each term is smaller than 2*sqrt(n)
Therefore, all square roots up to n are uniquely represented as part of a continued fraction expansion as a0 + 1/(a1 + 1/ (a2 + ...)) ... up to a[Lm(n)].
If we transform this nested fraction into a decimal number, any modification of this fraction will necessarily lead to a delta in the number by at least (a[Lm(n))]^-(Lm(n)), which is at most 2sqrt(n)^-(sqrt(n)
Therefore, accurately computing the square root up to the most significant digit of 2sqrt(n)^-(2sqrt(n)) will yield a result distinct from any square root up to n.
In the case of a sum of square roots, assuming that n is the largest root, accurately computing the sum up past the most significant digit of 2sqrt(n)^-Lm(n) will be sufficient to decide if a sum of square roots is larger than or smaller than another.
2sqrt(n)^-Lm(n) is reciprocally subexponential, thus the number of digits needing to be computed will grow sub-linearly with n
Therefore, the problem can be solved in polynomial time.