51–60 of 189 posts
This looks more like a problem with ( my understanding of ) complexity theory in general. Categorizing problems by "The size of the input" is too imprecise when irrational numbers are a part of the problem.
I would say that imprecision is somewhat artificially induced by the fact we so thoroughly use IEEE floats that we tend to assume that they are the only numbers. When invoking arbitrary-precision floats (or equivalent), pretty much all numerical calculations get a lot harder than we intuit instantly. So much as comparing one number to another without taking a square root goes from O(1) to O(n) for n = the representat…
Novice: "O(n), because you have to iterate from 0..n."
Expert: "O(log n), because we can use matrix exponentiation."
Master: "O(n), because F(n) has O(n) digits to print!"
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
sqrt(1-x) = 1- \sum_n C(n)/2^(2n+1) x^(n+1)
where x is in (0,1) and C(n)=binomial(2n,n)/(n+1) is the n'th catalan number.
[Learned this from http://www.math.chalmers.se/~wastlund/coinFlip.pdf]
This problem is a perfect example of better is the enemy of good enough. What's striking here is that the simple FP64 solution is for the most part more than good enough for any practical application you would find working in Tech. Anything beyond that is likely unnecessary gold plating. 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…
Earlier quoted context omitted.
It is a specific statement by Liouville: if you can approximate a number "very well" using rational numbers, then it must be transcendental. https://mathworld.wolfram.com/LiouvillesApproximationTheorem... My statement above may be a bit confusing, though.
They are using a different notion of “measure” than the standard notion of absolute value of the difference. Under the standard measure every number is within epsilon distance of a rational for any positive epsilon. Thank you for the clarification.
I was replying to the previous comment which seemed to imply that knowledge.
Earlier quoted context omitted.
Input length in binary is the standard way to calculate computational complexity. Sometimes we handwave that away, but in problems like this where the size of the number matters, we stick to the more strict definition of computational complexity. Number in binary vs number in decimal doesn't make a big difference because it's just a constant factor.
Thanks really. I guessed as much. What about the other questions? How do you get to an input length from a list of numbers? Just concattenate all their binary digits? Can you answer any of these?
> 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…
It seems that the degree of minimal polynomial having as root the sum of N square roots might be up to 2^N, and if you then apply the bound at https://en.wikipedia.org/wiki/Geometrical_properties_of_poly... (where n = 2^N) you get a bound on the order of at least 2^N digits (more precisely 2^N (N + D)).
So it doesn't seem to lead to a proof of a subexponential number of equal digits, unless the degree of the minimal polynomial is actually subexponential.
(sqrt(a_1) + sqrt(a_2) + ...)*(sqrt(b_1) + sqrt(b_2) + ...) = (sqrt(a_1*b_1) + sqrt(a_1*b_2) + ... + sqrt(a_2*b_1) + sqrt(a_2*b_2) + ...).
sumOfSqrts(xs) * sumOfSqrts(ys) = sumOfSqrts(convolution(xs, ys))
NB: the article describes PSPACE as being definitely larger than P or NP. But, just like how we don't know (but strongly suspect) NP is bigger than P, we don't know if PSPACE is bigger than P! Complexity theory is hard, so much so that even these relatively simple questions haven't yet been proven.
> There’s a known, reasonably fast algorithm (in BPP) for checking equality of sums of square roots What is it?
You just have to take out square factors from each, and combine terms with matching sqrt(n), and that will be unique
Now, you can subtract equal terms from each side of the equation and if you can reach 0=0 then the numbers are equal. If you're left with something like sqrt(3) = 5 * sqrt(2) the the numbers are unequal.
This stems from the fact, that I give without proof, that for integers X, Y and Z that contain no squares that sqrt(x) + sqrt(y) is never equal to sqrt(z). So there's no way to (say) add a bunch of square roots of 2 and have it become equal to a square root of 3 or 5.
A number contains no squares if its prime factorization contains no repeated factors. Since this seems to involve factorization, plus a step of matching up numbers from both sides, the computational complexity would seem to be at least the complexity of factorization. The term-matching step is presumablty the easier step of the two.
> 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…