Comment by akoboldfrying
3 hours ago
I don't really understand. The fact that, until now, no one's been able to come up with a better algorithm than the one everyone thinks of in 15s is what makes it an interesting conjecture.
It's made more tantalising by the fact that O(n^2) is so much larger than O(n) (the obvious lower bound needed to read the input), which suggests "room" for "something clever to do better".
It's the "Nobody thought this was possible" that I found curious. Yes, there is a lot of room between O(n) and O(n^2)! That's why it seems strange that it would be thought impossible.
But I guess it is just that people have been working on it for a long time with no progress, and so the thought was that there must be something especially hard about it. And, well, there is something comforting about round numbers, and so O(n^2) is something special, whereas if the O(n^1.9992) algorithm was known from the start I doubt anybody would have been surprised if O(n^1.9991) was possible.