On: List of unsolved problems in computer science

the problem is that while dropping from n^2 to n log n is a big deal, dropping from (n log n) to n won't help much if you end up increasing the constant costs at the same time.

It will eventually. Practical problems are pretty much solved.