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.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

2 thoughts on “When has a problem been solved?”

  1. Some notes:

    – I’d give a Nobel Prize to anyone who could reduce global warming/decrease cancer rates/improve worldwide health by 1%.

    – Spam will always have a precision/recall tradeoff, I think. I can stop your FP rate by blocking your access to mail.

    – Spammers will continue to improve, so an ‘order of magnitude’ improvement might just be to stay at a current annoyance level.

    – The definition of ‘spam’ will always fuzzy, as well.

    – I dislike your spam protection 🙂

  2. I like Daniel’s high level perspective: researchers should focus on work that has room to have a big effect. Once we get down to the minor details it’s hard for researchers to have much of an impact, because the actual environment in which the research is deployed may matter more than the algorithm/interface/whatever discovered by the researcher.

    OTOH, I’m not sure there’s a “order of magnitude” definition that we’re all going to agree to. I think it’s very dependent on the domain, and the needs of users within that domain. To me the key question is: will this research, if it succeeds, change the user experience in a qualitative way? If so, I’m interested; if not, less so.


Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax