So let’s say we start with computing the square roots to X digits of precision after the decimal point. Then we add up lower and upper bounds, giving us interva

So let’s say we start with computing the square roots to X digits of precision after the decimal point. Then we add up lower and upper bounds, giving us intervals for the sums over the two lists. If those intervals overlap we have to go back and compute e.g. 2X digits of precision, and so on. But in most cases we’d be done after the first iteration. Seems to me that would be polynomial in the average case. The worst case could of course be really bad. But if you’re telling me you know for sure that it’s exponential, then you must know something about the existence of lists with very close sums. As I understood the OP we don’t know if such lists exist. So average time complexity is polynomial and worst case is unknown. EDIT: Doesn’t https://www.sciencedirect.com/science/article/abs/pii/S0020019006001396?via%3Dihub https://www.sciencedirect.com/science/article/abs/pii/S00200... show that this algorithm is in fact polynomial?