Analyzing the Zoo

Greg Kuperberg wrote software that runs transitive closure and other tricks on the Complexity Zoo to produce inclusion diagrams and a list of complexity class relations. Kuperberg's project has great value, the ability to tell immediately whether one class is contained in another can save us time rederiving these results and gives us a clearer picture of how complexity classes relate to each other.

Kuperberg's software also produces a large number of open questions, finding the most and least likely open relativizable containments.

Go through the list of open questions and you will find some problems that follow from known results. Let Greg know and he will update his program, which of course might list other known "open" questions, but this process must converge in a finite amount of time.

You can also find some interesting open questions you might not have thought about and you'll also find a number of long-standing open questions.

But mostly you will find problems that just don't look that interesting. Why? Kuperberg's software treats complexity classes as syntactic objects, all of equal importance. But every class has a story, invented for a reason such as to capture an interesting computation model, to understand the complexity of some real world problems, or just to help us understand the relationship of other classes. Many classes get less interesting over time because the reasons we invented them have changed. Comparing two classes developed in very different contexts, say quantum classes and crypto-based classes, doesn't give us much insight unless the classes are extremely common. Finally in most cases we expect a separation and usually one gets little credit for the effort to create an oracle to get a separation we already expected.