This work is licensed under a
Creative Commons License.
|
Monday, August 28, 2006
Analyzing the Zoo
Posted by Lance
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.
7:58 AM
# 4 comments
-
Which classes are crypto-based? Well, P!=UP if there exist worst-case one-way functions, but (almost) nobody cares about them anyhow...
-
I assume Lance meant things like CZK (the class of languages admitting computational zero knowledge proofs).
-
I haven't updated my own complexity diagram in a while so here is the GraphViz source if anybody wants it.
-
Thanks a whole lot for plugging my complexity zoology project.
To clarify one point, there is a big difference in the tables between open cases and blank cases. There are not all that many open cases and I would suppose that they are generally interesting questions, or closely related to interesting questions. Although I have not written software to generate a reasonable list of citation for a single case, everything marked as open can be traced to a person or a paper. If you solve one of these, then I can tell you the relevant citations so that you can see if it is a publishable result.
On the other hand, there are also blank cases. These are cases where my database is missing information and does not even know whether the question is open. They are indeed mostly boring. Usually there is a completely standard oracle separation that no one has bothered to write down, for instance because the classes in question are not closely related. However, it would really be helpful to fill in data for all extremal blank cases. The code is designed so that no one needs to fill in everything in the middle. It knows that if X implies Y implies Z and X and Z are open problems, then Y is also an open problem. That kind of trick (for inclusions and separations as well as open cases) is what allows the project to scale to hundreds of complexity classes.
You can think of the blank cases as uncharted regions on a geographical map. Of course they are mostly boring, but the map is much nicer if everything is filled in. If you can help me fill in the blank cases, then great, please let me know.
Also everyone should take a look at the Javascript/SVG-powered "active diagram" using either Firefox 1.5 or Opera 9. (It doesn't work with Internet Exploder.) That is where the robozoologist's knowledge really leaps out at you.
Links to this post:
Weblog Home
Archives
