Automating the Zoo
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.