4 ms·

Exhibiting an algorithm for any real problem with O(n^k) complexity for k>>1 would be interesting. This is one of the many interesting aspects of this problem.

by lisper 5y ago

Exhibiting an algorithm for any real problem with O(n^k) complexity for k>>1 would be interesting. This is one of the many interesting aspects of this problem. In the real world, for problems people actually care about, k is invariably small, like <<100 and no one knows why. This is one of the many, many vexing aspects of this problem.

skissane 5y ago
What about page 4 of [0]: > We remark that, while polynomial, the running time of the algorithm is somewhat abysmal; loose estimates places it somewhere around O(n^(10^100)); the running time of the algorithm of [RT12] is similar. I don’t know if that counts as a “real problem”, and I suppose it is only a “loose estimate” too. [0] https://arxiv.org/pdf/1205.0458v2.pdf https://arxiv.org/pdf/1205.0458v2.pdf
- lisper 5y ago
  No, I think that definitely counts as a counterexample. Wow. TIL.
bawolff 5y ago
Intuitively i feel like it makes sense though. The k in O(n^k) roughly corresponds with how many times you loop through the data. Its really hard to imagine a useful algorithm where you need to loop through the data exactly 153 times but then stop there. Either you're going to need to grow the number of loops with input size (be exponential) or surely you got all the data you needed the first 14 times you went through the data. I guess that's not really very rigorus it just feels intuitively right. I just can't imagine a system where you always gain new information regardless of input size on loop iteration 561, but never on iteration 562. Its somewhat similar to how in pure math problems where it seems kind of suspicious if the answer is something like exactly 8.3781 and the problem statement didn't have any related constants in it. Integers are expected, Irrational numbers are expected, decimals with exactly 4 digits sound suspicious.

by lisper 5y ago

skissane 5y ago

What about page 4 of [0]: > We remark that, while polynomial, the running time of the algorithm is somewhat abysmal; loose estimates places it somewhere around O(n^(10^100)); the running time of the algorithm of [RT12] is similar. I don’t know if that counts as a “real problem”, and I suppose it is only a “loose estimate” too. [0] https://arxiv.org/pdf/1205.0458v2.pdf https://arxiv.org/pdf/1205.0458v2.pdf

lisper 5y ago
No, I think that definitely counts as a counterexample. Wow. TIL.

bawolff 5y ago

Intuitively i feel like it makes sense though. The k in O(n^k) roughly corresponds with how many times you loop through the data. Its really hard to imagine a useful algorithm where you need to loop through the data exactly 153 times but then stop there. Either you're going to need to grow the number of loops with input size (be exponential) or surely you got all the data you needed the first 14 times you went through the data. I guess that's not really very rigorus it just feels intuitively right. I just can't imagine a system where you always gain new information regardless of input size on loop iteration 561, but never on iteration 562. Its somewhat similar to how in pure math problems where it seems kind of suspicious if the answer is something like exactly 8.3781 and the problem statement didn't have any related constants in it. Integers are expected, Irrational numbers are expected, decimals with exactly 4 digits sound suspicious.