The predicates < and > are strictly semidecidable, meaning that if two real numbers are equal to each other, then no algorithm is guaranteed to terminate. The c

The predicates < and > are strictly semidecidable, meaning that if two real numbers are equal to each other, then no algorithm is guaranteed to terminate. The complexity is thus RE, which is worse than PSPACE. But the real numbers which show up in the sum-of-square-roots problem are from being as general as possible, so the complexity is PSPACE at worst. The foundations needed to understand general real number computation are listed here: https://news.ycombinator.com/item?id=30057794 https://news.ycombinator.com/item?id=30057794