One of my favourite internet resources is Scott Aaronson’s Complexity Zoo, a compendium of pretty much everything that is known about computational complexity classes. I’m a physicist, and don’t have a huge need for this kind of thing, but even so, I find it surprisingly useful, surprisingly often. When I want to know something about complexity classes, the Zoo is the second best resource I know of. Of course, the best resource is to ask Scott (or another suitably inclined computer scientist) directly.
But such people aren’t always around. An interesting idea for a project that came up in conversation with Tereza Tušarová and Dan Kenigsberg last week is to produce a front end for the Complexity Zoo: a natural language interface, ideally capable of automated reasoning, and perhaps even of producing non-trivial proofs, or telling you interesting things (“yes, the inclusion you propose is possible, but the polynomial hierachy would collapse”). Unfortunately, I don’t have time to do this, but just thought I’d mention it here, in case anyone interested in symbolic mathematics were looking for a fun project.
I don’t know about the natural language interface, but perhaps a form that looks like this:
, ,
would be an easier start. Then you click the “what is known?” button, some ruleset runs, and presto, you have an answer. (Wonder how difficult it is to evaluate that ruleset in general, given only the constraints we know about complexity classes so far?)
If we’re asking for bluesky projects, though, something that takes a problem and looks for reductions from X-complete problems for complexity class X would be more useful. After all, if you come across a new problem, you’d like to know roughly how hard it is and which classes might be relevant. I was recently surprised to learn, for example, that matrix powering is hard for the class GapL, because I hadn’t heard about GapL before.
OK, that didn’t come through. I mean a form that looks like
“menu for class A”, “relation”, “menu for class B”
David: You’re right, of course, that there would be much better ways of doing this than via a natural language interface. (Where “better” = functionally almost equivlaent results for far less effort.)
I actually wrote it that way because of a rather frivolous joke in the original conversation with Thereza and Dan that suggested this – we were talking about how useful the Complexity Zoo is, and I joked that Scott himself provided a wonderful natural language interface to the Zoo. Which started us thinking…
Jokes can be useful stimuli to research. I co-authored a paper years ago where the main result was suggested by a joke.