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 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".
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.
Eg here's a paper with a bunch https://people.csail.mit.edu/virgi/6.1420/papers/gajovermars...
So every grad student who has thought about geometry problems will have spent more time than they're proud to admit thinking about better algorithms only to realize it's 3sum hard.
It's not just "people have thought about one problem a bunch" - the whole class has been wailed on to no avail