One topic that comes up on a regular basis is the question of how to come up with open problems that might be suitable for tackling. Of course everyone knows about P vs. NP, and like Fermat’s Last Theorem in number theory, this problem can serve as motivation for studying the foundations of computational complexity. However, as was the case with FLT, it is not a problem that a student would hope to make any real progress against. One difficulty with identifying problems that are hard enough to be interesting, but not so hard as to be hopeless, is that the people who are familiar with such problems might be reluctant to advertise them–they understandably might want to tackle the problems themselves first, or in the case of faculty, to give the problems to their students to work on.

So it was especially nice to learn (via David Eppstein) about the Open Problem Garden created by Matt DeVos and Robert Šámal. The Garden is a wiki-style repository of open problems from math and computer science, so anyone can register and contribute their own entries. Problems are categorized by subject (graph theory, combinatorics, etc.), and rated according to importance. Problems are not rated for difficulty per se, but there is a yes/no indicator for whether the problem might be suitable for an undergraduate student. It looks like the database was preloaded with the problems from Bojan Mohar’s Problem of the month page, so it is currently heavily weighted toward graph theory. I’m really hoping that as time goes on, people in the TCS community will use this repository to store their own open problems.

There is as of this writing a single entry in the TCS subject category: Subset-sums equality. This search variant on the NP-complete decision problem SUBSET-SUM is one which I haven’t seen before. Unfortunately, the entry does not currently contain much background or any references, so perhaps if someone reading this is in the know, they could flesh out the entry a bit. (A quick search turns up this article on finding approximate solutions to the problem.)

While I’m searching around, perhaps I should look for other sources of open problems… Unfortunately, a lot of the hits returned by Google are pages describing P vs. NP and not much more (including, surprisingly, this Wikipedia article). Open problems have been discussed on at least a couple of occasions on the Computational Complexity blog, here and here. In fact, in the comments to that second post, Matt DeVos puts in a plug for the Open Problem Garden (which was in beta at the time). That was back in March, and evidently no one in the meantime has been sufficiently motivated to add any additional TCS open problems. Pity, that.

Finally, for something of a slightly different flavor, here is David Johnson’s Challenges for Theoretical Computer Science. Instead of a list of conjectures to be proven, this is a list of broad challenges for computer science, perhaps reminiscent of David Hilbert’s list of problems for mathematics.