4 ms·
Doesn't this imply that every algorithm that compares real numbers is in PSPACE?
by blackbear_ 5y ago
Doesn't this imply that every algorithm that compares real numbers is in PSPACE?
- ogogmad 5y agoThe 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
- blackbear_ 5y agoSuper interesting, thanks a lot fot the resources!
- lupire 5y agoReal numbers are slippery, because almost no real numbers are computable, even approximately. This conjecture only applies to numbers that have small descriptions but complicated values. If you don't have simple names for your real numbers, then the algorithms are trivial, because all the complexity is in writing the input!
- adgjlsfhk1 5y agoNo. That said, most are at least that bad.