7 ms·

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 whe

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.

qsort 5y ago
Why would it be too imprecise? I agree there are some (many?) problems with some definitions used in complexity theory, but "size of input" is certainly not part of the problem. It can be defined very precisely. I don't see the slightest problem with how it's framed.
- dooglius 5y ago
  So what is N here? The sequence length, number of digits across all sequence elements, sum of all elements?
  - deleted 5y ago
    [deleted]
  - qsort 5y ago
    N is the sum of the lengths of the elements of all lists, when all elements are written in binary (or any other base, which is the same up to a constant).
Khoth 5y ago
Irrational numbers are involved in the problem, but not in the the size of the input, which is a list of natural numbers. There are a number of reasonable ways to encode such a list but they'll all scale in more or less the same way and be equivalent when looking at big O notation.
deleted 5y ago
[deleted]
Frost1x 5y ago
If you assume that mathematical notation (language) doesn't abstract complexity in a uniform fashion (something you can write and capture meaning with a few symbols isn't inherently more or less complex than something you can write with a lot of symbols), it becomes pretty obvious that something isn't necessarily as simple as it may look at the surface. Having worked in computing for long enough, I'm well aware of this fact in the world of estimating time (which to some degree is estimating complexity) to address a given problem request. I can very easily write down in English a pretty generalized description that you need to: cure any and all forms of cancer. That's a fairly concise request, I can write it in one line, but it hides a mountain of complexity needed to accomplish that. It also doesn't describe what we consider as "cure" or "cancer" which can be ambiguous in some cases. Much of the same is true with seemingly cute conjectures that seem to capture a behavior that may be incredibly complex to prove (if not impossible, e.g. Godel). The Collatz conjecture comes to mind where Paul Erdos famously said something to the effect of "Mathematics may not be ready for such problems."
jerf 5y ago
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 representation of the shortest of the two numbers. Our IEEE-based intuition sees that and goes wha? But you can also build a separate intuition based on the arbitrary representation that would make this easy to both understand and intuit. It's really easy to get into PSPACE with arbitrary precision. Heck, it's pretty easy to get into EXPSPACE and almost any other prefix to "SPACE" you want, because it's easy to stipulate very close numbers and transforms on those very close numbers that require obscene precision to be sure you're correct. If you work in this sort of mind space all the time, it's perfectly precise to talk about arbitrary-precision numbers. But the real universe we live in bottoms out at 10^-35 meters or so, our practical ability to be precise a dozen or two orders of magnitude sooner than that at a minimum (and often another dozen for macroscopic work), and the practical impact of this is minimal because in practice, the first Haskell solution in that post is essentially correct in our real universe 99.9% of the time, even though it is glaringly wrong mathematically, because in the real universe we never have hundreds of digits of precision, and that's where our intuition is built.
- nemo1618 5y ago
  Good example of this: What is the complexity of the fastest algorithm that prints the nth Fibonacci number? 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!"
  - thomasahle 5y ago
    The Master's argument would imply Ω(n) time, The matrix exponentiation algorithm would take O(nlogn) time, since you have to multiply large numbers, and this takes nlogn with the best known algorithms (FFT). I don't think there are any O(n) algorithms.
heavenlyblue 5y ago
Have you read the article? The author explicitly defines what the question is (and how the question of irratonality of numbers is resolved there). As a matter of fact they explicitly mention that the algorithm in question only requires polynomial memory space to compare N sums of roots of arbitrary numbers.

qsort 5y ago

Why would it be too imprecise? I agree there are some (many?) problems with some definitions used in complexity theory, but "size of input" is certainly not part of the problem. It can be defined very precisely. I don't see the slightest problem with how it's framed.

dooglius 5y ago
So what is N here? The sequence length, number of digits across all sequence elements, sum of all elements?
- deleted 5y ago
  [deleted]
- qsort 5y ago
  N is the sum of the lengths of the elements of all lists, when all elements are written in binary (or any other base, which is the same up to a constant).

Khoth 5y ago

Irrational numbers are involved in the problem, but not in the the size of the input, which is a list of natural numbers. There are a number of reasonable ways to encode such a list but they'll all scale in more or less the same way and be equivalent when looking at big O notation.

deleted 5y ago

[deleted]

Frost1x 5y ago

If you assume that mathematical notation (language) doesn't abstract complexity in a uniform fashion (something you can write and capture meaning with a few symbols isn't inherently more or less complex than something you can write with a lot of symbols), it becomes pretty obvious that something isn't necessarily as simple as it may look at the surface. Having worked in computing for long enough, I'm well aware of this fact in the world of estimating time (which to some degree is estimating complexity) to address a given problem request. I can very easily write down in English a pretty generalized description that you need to: cure any and all forms of cancer. That's a fairly concise request, I can write it in one line, but it hides a mountain of complexity needed to accomplish that. It also doesn't describe what we consider as "cure" or "cancer" which can be ambiguous in some cases. Much of the same is true with seemingly cute conjectures that seem to capture a behavior that may be incredibly complex to prove (if not impossible, e.g. Godel). The Collatz conjecture comes to mind where Paul Erdos famously said something to the effect of "Mathematics may not be ready for such problems."

jerf 5y ago

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 representation of the shortest of the two numbers. Our IEEE-based intuition sees that and goes wha? But you can also build a separate intuition based on the arbitrary representation that would make this easy to both understand and intuit. It's really easy to get into PSPACE with arbitrary precision. Heck, it's pretty easy to get into EXPSPACE and almost any other prefix to "SPACE" you want, because it's easy to stipulate very close numbers and transforms on those very close numbers that require obscene precision to be sure you're correct. If you work in this sort of mind space all the time, it's perfectly precise to talk about arbitrary-precision numbers. But the real universe we live in bottoms out at 10^-35 meters or so, our practical ability to be precise a dozen or two orders of magnitude sooner than that at a minimum (and often another dozen for macroscopic work), and the practical impact of this is minimal because in practice, the first Haskell solution in that post is essentially correct in our real universe 99.9% of the time, even though it is glaringly wrong mathematically, because in the real universe we never have hundreds of digits of precision, and that's where our intuition is built.

nemo1618 5y ago
Good example of this: What is the complexity of the fastest algorithm that prints the nth Fibonacci number? 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!"
- thomasahle 5y ago
  The Master's argument would imply Ω(n) time, The matrix exponentiation algorithm would take O(nlogn) time, since you have to multiply large numbers, and this takes nlogn with the best known algorithms (FFT). I don't think there are any O(n) algorithms.

heavenlyblue 5y ago

Have you read the article? The author explicitly defines what the question is (and how the question of irratonality of numbers is resolved there). As a matter of fact they explicitly mention that the algorithm in question only requires polynomial memory space to compare N sums of roots of arbitrary numbers.