Monday, October 05, 2009

State the open problems!

A few incoming paper-review requests remind me of the following long-standing gripe.

A nice feature of theoretical computer science is that the results we obtain tend to raise lots of very well-defined research questions. I'm very much in favour of the practice of stating these open problems in detail, in our research papers. Indeed, a thorough discussion of future work is arguably as important as including references to all appropriate previous papers -- the latter puts you in touch with the past and the former makes the connection with the future. Some papers take a lot of care to spell out what the open problems are, but some (most?) don't bother. Maybe the authors think it should be obvious what the open problems are. Occasionally they perhaps don't want the reader to pick up on an open problem they've got lined up for a follow-up paper.

Let's consider the case where the open problem being raised is "obvious". For instance, suppose you give an algorithm that approximates some objective within a factor of 2.5. Clearly, any approximation ratio of better than 2.5 is (implicitly) raised by the paper's result, so why bother to point it out? I would say it usually is worth pointing out, partly just to confirm that you really would find further progress to be interesting, and partly because you might have some useful additional discussion to add, such as a consideration of the prospects for improving beyond a ratio of 2, say.

If someone writes a paper that is able to claim to have solved an open problem stated explicitly in a previous work, that's usually a good piece of relatively objective evidence that the result is interesting. Most papers do not manage to achieve this - they usually solve some variant of an open problem posed previously, and indeed "posed" may just mean implicitly rather than explicitly. This is, there is a scarcity of "official" open problems (those that have been raised and deemed to be interesting in a published paper).

(There are some web sites that help, e.g. Comp geometry problems has links to other open problem pages. Open problem garden: wiki for general math problems.)

3 comments:

Jeffe said...

Now you're making me feel guilty for not updating my open problem web site in forever.

Anonymous said...

If someone writes a paper that is able to claim to have solved an open problem stated explicitly in a previous work, that's usually a good piece of relatively objective evidence that the result is interesting.

Actually, I find it a real problem when a paper's importance becomes "inflated" (whether during the review process or afterward) just because it answers a question that happened to be raised explicitly in a prior work. A question is interesting if it's interesting, not because it was in a list of questions in a random paper.

Paul Goldberg said...

In response to comment 2:

Yes, I suppose there is a risk that a dull, unimportant problem can get talked up in papers, but for myself, I don't find that to be widespread. And, undoubtedly there are many unstated questions whose intrinsic interest should commend itself to any right-minded scientist (indeed, the ones I have come up with in the past, clearly belong to this class :-).