31–40 of 189 posts
Doesn't this imply that every algorithm that compares real numbers is in PSPACE?
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!
What does “ compute this as a function of the length of the input encoded in binary” mean? Can someone explain it with the other sample used in the article? Does it mean the input will be provided in binary form instead of decimal? How does that change things?
"How quickly can we compute this [this = the solution to the problem], as a function of the length of the input encoded in binary?"
i.e. it's just wondering what's the computational complexity. The input can be provided in any base, it makes no difference.
What does “ compute this as a function of the length of the input encoded in binary” mean? Can someone explain it with the other sample used in the article? Does it mean the input will be provided in binary form instead of decimal? How does that change things?
> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to establish some kind of bound on this. Like, maybe we should be able to say “if you add two lists of n numbers, each of which has d digits, then they can’t disagree for more than k * n * d digits” for some k. But no-one’s been able to prove anything like this. You c…
I guess the problem can be solved using what you say, certainly.
It is only transcendentals that can be "too near" each other, and near rationals (this is Liouville's result, which was improved later on, in a specific case the one you say).
It probably has been tried already by someone, but how about this: all square roots can be written as repeating continued fractions [1]. With a bit of work, continued fractions can also be summed [2] and compared. Wouldn't this take less than exponential time? [1] http://benpaulthurstonblog.blogspot.com/2012/05/estimating-s... [2] https://www.jstor.org/stable/1969389
If I were asked this on a job interview and they didn't accept that answer and started going on about me missing the pure math here that would be a great sign that such a place probably doesn't ship things very often. I would also bring up that no one can solve the traveling sales problem either but that approximately optimal solutions run the world of logistics on a daily basis.
Yet much like you can dedicate an entire supercomputer to calculating the energy of two hydrogen atoms to arbitrary precision, it's a really interesting problem with respect to the pure math. But come on, the guys most likely to bring this question up are relying on 16-bit floating point to train their neural networks.
Exponent.Mantissa.Boom. In practice, I know just about no one anymore who can tell me the format of 32-bit or 64-bit floating point because they're so used to abstracting that away.
It is always fascinating how many problems that are simply stated are difficult to solve. Whenever I see something like this I try and think about what the repercussions would be if an efficient algorithm did exist, and that helps to understand where the complexity is. In this case I believe there would be many problems in computational geometry involving Euclidean shortest paths that would be made trivial by an effi…
Why would one try to formulate it as a function of the input length in binary? Does this have a practical relevance? Why not think about it in terms of the numbers given in decimal, their count and their size? And what is the input length in this problem? The numbers encoded in binary? Pretty sure it cannot be computed by just looking at how many numbers are given in each list.
Number in binary vs number in decimal doesn't make a big difference because it's just a constant factor.
Doesn't this imply that every algorithm that compares real numbers is in PSPACE?
> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to establish some kind of bound on this. Like, maybe we should be able to say “if you add two lists of n numbers, each of which has d digits, then they can’t disagree for more than k * n * d digits” for some k. But no-one’s been able to prove anything like this. You c…
Exactly: algebraic numbers, despite not being periodic, are in general "reasonably far from each other", and especially from rationals. I guess the problem can be solved using what you say, certainly. It is only transcendentals that can be "too near" each other, and near rationals (this is Liouville's result, which was improved later on, in a specific case the one you say).