When has a problem been solved?

I have stated before that researchers should focus on new problems or on providing solutions that are at least an order of magnitude better than previous solutions. There is a catch to this statement: it says that if you are within an order of magnitude of the ultimate answer, then you should stop, unless, maybe, you can prove that you have achieved the ultimate solution. Proving you have the best possible solution whereas others were providing approximation does constitute a significant gain, certainly worth publishing, but this is rarely possible. Most real problems are too complex to allow our puny brain to prove that a solution is ultimate.

So do we just accept that being within an order of magnitude of the answer is good enough? If you are within an order of magnitude of perfection with respect to all indicators, simultaneously, then maybe you ought to stop. Yes?

Another catch to this is that you may not know exactly how far off you are from the best solution. It might be very difficult to study the characteristics of the ideal solution. What then? Do we still hold off on publishing incremental improvements to existing solutions? Do you call the problem solved if, over a long period of time, nobody was able to improve the state-of-the-art by an order of magnitude?

Food for thoughts: Recently, John Riedl asked on his blog whether we could tell when spam filters would get to be good enough. My immediate answer was to apply the Turing test: a spam filter is good enough when it has achieved a human-level of performance. Yet, I know this is not the answer. Nothing is ever perfect, but my level of performance is far from the ultimate goal. I doubt spam filters will ever pass my Turing test, but even if they did, I am likely not to be satisfied. One false positive is still one too many.