[abetusk]

Sorry to be obtuse, but I don't understand your hesitation.

If you have a lower bound on the absolute value of the smallest difference of any/all pairs of roots, the lower bound on the sum of N of them is at most adding lg(N) bits.

EDIT:

I'm wrong, you're right. You've hit it on the head. My apologies.

Just because there's bounds on pairwise roots, doesn't mean they then can be bounded when they're all summed together.

In other words, say you have d_0 = |a_0 - a_1| and d_1 = |a_2 - a_3|, you might get into a situation where |d_0 - d_1] requires some exponential number of bits to represent.

[tgflynn]

I don't see the problem. Once you have enough bits to resolve every pairwise difference you're just reduced to the problem of comparing the sums of two lists of n bit integers and I'm pretty sure that's in P.

If it's not then that should be the main point here, sqrt has nothing to do with it.

EDIT: You also know what the largest possible error is on each pairwise delta so if you add log(N + 1) bits you handle even the worst case where one sum is +N x maxerror and the other -N x maxerror.