Friday, July 13, 2007

Open problems wiki

From the computational complexity blog I find out about a new web site where you can upload, discuss and view open problems in mathematics. At present there is just one problem filed under theoretical computer science. (It's not the obvious one either. As it happens it's one that's related to my own research topic, namely the computational complexity of EQUAL SUBSETS, which is a total search problem, in common with the search for Nash equilibrium. In giving talks in the past, I have used EQUAL SUBSETS to explain what is meant by a total search problem.)

I like open problems. To me, anything that's been described as an open problem, becomes an exciting challenge. Most papers in theoretical computer science, including most papers that I have written, do not solve open problems - they just solve problems that have been invented by one of the co-authors. I believe there should be a greater emphasis on the solution of recognised open problems as being a sign of high quality of a mathematical paper. I admit, there's always going to be a bit of subjectivity in judging this measure of quality - you have the problem of deciding whether an "open problem" has really been stated (it's easy to state them implicitly, as opposed to explicitly, in papers). Also, there's the issue of recognition of partial solutions, and to what extent they pave the way to complete solutions.

Regarding the web site itself, this is something that may just catch on, and then again, may fail to do so, as discussed in the complexity blog. It requires a "critical mass" of contributions in order to gain enough recognition. The design of the web site seems nice. The importance of open problems gets rated on a 4-point scale; it's not clear to me how that is chosen - a good web site of this nature should have some clever mechanism so that members of the community can vote on that issue.

No comments: