Run free, my animal friends!
In August of 2002 I opened the Complexity Zoo: an online bestiary of 196 complexity classes, since expanded to 443. Yesterday I entrusted the Zoo to anyone on Earth who wants to feed the animals or contribute their own. This was possible because of John Stockton, who graciously converted the Zoo to wiki form.
The decision to relinquish control of my best-known work was tinged with regret. But at age 3, my baby is all grown up, and it’s time to send it off to grad school so I can move on to other things.
This seems like a good occasion to ask a potentially heretical question:
Did theoretical computer science take a wrong turn when it introduced complexity classes?
For readers with social lives, I should explain that a “complexity class” is a class of problems solvable by some sort of idealized computer. For example, P (Polynomial-Time) consists of all problems that an ordinary computer could solve in a “reasonable” amount of time, meaning an amount that increases like the problem size raised to a fixed power. To illustrate, a few years ago Agrawal, Kayal, and Saxena made international headlines for showing that “PRIMES is in P.” What this means is that they found a general method to decide if an n-digit number is prime or composite, using only about n12 steps — much less than you’d need to try all possible divisors. Faster methods were known before, but they had a small chance of not producing an answer.
Other complexity classes include PSPACE (Polynomial Space), BQP (Bounded-Error Quantum Polynomial Time), EXP, NP, coNP, BPP, RP, ZPP, PH, Ξ£2P, P/poly, L, NL, PP, AWPP, LWPP, BQNC, QMA, QCMA, S2P, SZK, NISZK, and many more.
The advantage of this alphabet soup is that it lets us express complicated insights in an incredibly compact way:
- If NP is in BPP then NP=RP.
- If NP is in P/poly then PH = Ξ£2P.
- PH is in P#P.
- NL=coNL.
The disadvantage, of course, is that it makes us sound like the fabled prisoners who tell each other jokes by calling out their code numbers. Again and again, I’ve had trouble getting across to outsiders that complexity theory is not “about” capital letters, any more than chemistry is “about” weird strings like NaCl-KCl-MgCl2-H20. Why is it so hard to explain that we don’t worry about EXP vs. P/poly because we’re eccentric anal-retentives, but because we want to know whether a never-ending cavalcade of machines, each richer and more complicated than the last, might possibly succeed at a task on which any one machine must inevitably founder — namely, the task of outracing time itself, of simulating cosmic history in an eyeblink, of seeing in the unformed clumps of an embryonic universe the swirl of every galaxy and flight of every hummingbird billions of years hence, like Almighty God Himself?
(Alright, maybe I meant BQEXP vs. BQP/poly.)
In the early 70’s, there was apparently a suggestion that NP be called PET, which could stand for three things: “Probably Exponential Time,” “Provably Exponential Time” (if P!=NP), or “Previously Exponential Time” (if P=NP). If this silly name had stuck, would our field have developed in a different direction?
Follow
Comment #1 October 11th, 2005 at 12:06 pm
As a mostly newcomer to complexity classes, I think that they are just fine. The only real problem is that their evolution and nomenclature has been undisciplined. For example, PP is really a very different animal than BPP. In general the association between probabilistic and non-probabilistic classes is cavalier. There should instead have been a complexity class for all Markov maps that can be approximated in randomized polynomial time with high fidelity. Then BPP should have been defined as a “B” operator (Boolean interpretation with completeness and soundness thresholds) applied to this other kind of class.
Boolean, string-valued, and integer-valued classes are also a mess.
Looking to the future, a project like the Complexity Zoo could do a lot to retain or even restore discipline. But I am not sure that you are sending it to graduate school. You may rather be casting it out of the house to flip burgers for a while. But that’s okay; it can get more education later.
Comment #2 October 11th, 2005 at 1:21 pm
Hmmm, if the signature problem of complexity theory was determining whether “PET” problems are or are not “easy”, maybe more girls would be attracted to theoretical computer science? (Okay, okay, please don’t flame me over that… there’s a serious question buried somewhere under the surface there.)
400+ classes is an awful lot. How many of those do you suppose will eventually collapse together? For someone just learning this stuff, the Zoo can be a bit overwhelming. If you had to choose just, say, the 25 most important classes (based on whatever subjective criteria you like), what would they be?
Comment #3 October 11th, 2005 at 2:16 pm
Alright, Kurt, here’s my list of the 25 most important complexity classes, in no particular order:
P, BPP, P/poly, NP, coNP, NP intersect coNP, P^NP, TFNP, SZK, MA, AM, PH, PP, #P, PSPACE, EXP, NEXP, BQP, QMA, BQP/qpoly, L, NL, TC0, NC, AvP
Anyone want to offer an alternative list?
There are a few widely-believed collapses, like P=ZPP=RP=BPP and NP=MA=AM, as well as known ones like IP=PSPACE and L=SL. But besides those, I believe most classes in the Zoo will turn out to be distinct.
And no, I don’t expect that jokes like yours would help attract more women to theoretical computer science.
Comment #4 October 11th, 2005 at 2:24 pm
Greg: There have been attempts to define operators as you describe. See for example these scribe notes
http://theory.csail.mit.edu/~madhu/ST03/scribe/lect10.pdf
I don’t know where such operators appeared first. Maybe someone else does? Changing the terminology to use these operators uniformly, however, is likely to be an uphill battle. Especially because I wouldn’t be surprised
if we can find cases where the
traditional definition and the operator-applied-to-another-class
definition are slightly different.
Scott: The profusion of complexity classes strikes me as a symptom of
a deeper issue. The real issue is what you pointed out – we deal with endless definitional variations of what it might mean to “compute,” possibly on a “machine.” (I say possibly because of logical or group-theoretic characterizations of computation.)
Many of the complexity classes in the Zoo come about by tweaking an existing class in an interesting way. So long as this kind of tweaking is
one of the primary modes of inquiry for computational complexity, we will continue to have lots of distinguished objects that need names. Whether it’s through the Complexity Zoo or through something like Greg’s base-and-operator, I don’t know. I don’t think this is a bad thing.
Comment #5 October 11th, 2005 at 2:43 pm
About the Wiki zoo, may I suggest (if this can be scripted in a sane manner) to move each class into its own Wiki page? Besides being easier on slow browsers and internet connections, it will also help in maintaining tidiness (harder to mess up everything with one edit, and involved people being able to track only changes made to their pet complexity class).
With seperate pages people could also add alternative and/or partial index pages (such as “all classes thought to be in PH by order of their conjectured level”). I’m willing to try adding a couple too π
Comment #6 October 11th, 2005 at 3:11 pm
People have indeed made some progress with operators as in Madhu’s notes. This already helps keep order in the Zoo. This is part of what inspired my comment.
But I want something a little different. The standard approach is to define operators like “BP” from Boolean complexity classes to Boolean complexity classes. But there is a subtle misalignment between this formal definition and the real ideas. For example you get that ExistsBPP is not the same (relative to an oracle) as MA.
To understand the class MA, you need define the class “A” (for “Arthur”), not as a class of languages, but as a class of functions from inputs to probability distributions on the output bit. Then there is a Merlin operator “M” that adds a witness to the input to maximize the probability of true output. Then finally there is a “B” operator (not “BP” as in Madhu’s notes) that converts fuzzy output to strict Boolean output via thresholds. If people had defined things this way, then BPP would be expressed as B.A and MA would be expressed as B.M.A.
These operator ideas are somewhat optional for ordinary randomization. They would have helped a lot for the current proliferation of quantum complexity classes.
People could similarly have thought through integer-valued classes a lot better. People should have used the notation P_Z (inspired by the real complexity theory of Blum et al) for integer-valued polynomial time. With suitable use of subscripts for the value set of a complexity class, you could have had consistent notation for +P, #P, and GapP. They can all be made from a summation operator applied to P_R for different rings R.
Comment #7 October 11th, 2005 at 5:12 pm
Kurt- I don’t think knowing the definition of many many classes is necessary for a decent understanding of complexity theory. It’s not sufficient either, but that’s a longer discussion. It’s not necessary because most of the zoo classes are variations on a few themes.
Let’s define a complexity class. First, pick your building blocks–the ‘resources’. I’ll nominate the most important ones: time, space, randomness, nondeterminism. Next I’d throw in counting and length-based advice. That’s a good set (since I don’t really understand quantum resources,.I will assume they’re of no importance, and trade Scott’s Q-classes for parity-P).
Pick two, say, nondeterminism and randomness. We could combine them on an operator model, or thru oracle access of one to the other, or in an ad hoc way. An important choice (and arguably a variable ‘resource’ of its own) is the ‘intensivity’ of the combination: do we have all our randomness in one batch, and nondeterminism in another, or can they alternate many times and adapt to complement each others’ behavior? In the first case we get something like AM or MA
Comment #8 October 11th, 2005 at 11:48 pm
Eldar: We already have a separate “edit” page for each class. But I’ll see if we can put the classes themselves on their own pages as well.
Comment #9 October 12th, 2005 at 12:14 am
I think complexity theory is an incomplete, half-baked theory that gives me severe indigestion. You guys sorely need a decent classification theorem. An example of a beautiful classification theorem is Cartan’s classification of Semi-simple Lie Algebras. Without it, we would also be looking at a zoo of lie algebras with hundreds of specimens.
Comment #10 October 12th, 2005 at 12:36 am
“You guys sorely need a decent classification theorem.”
OK wiseass, prove one. π
Comment #11 October 12th, 2005 at 1:18 am
‘semi-simple Lie algebra’ is a well-defined term; ‘complexity class’ is an open-ended notion, which makes it less susceptible to comprehensive classifications but also more potent as a vehicle for creativity. It’s true there aren’t enough separations, but try asking why this might be the case rather than just belittling the theory,
Comment #12 October 12th, 2005 at 2:05 am
Here is my list of 15:
AC_0, NC_1, NL, LOGCFL, GapL, P, BPP, BQP, NP, AM, PP, #P, PSPACE. EXP, NEXP
Most likely next results: NL=LOGCFL and P=BPP. But we will see.
Could theory have taken a different direction? Of course. How can it be otherwise… After all, what is it that we do if not a random walk? How else can we explain the example you quote, “Primes in P” this late in the evolution of complexity theory.
Comment #13 October 12th, 2005 at 2:23 am
The last line got chopped out from the
prev post, which was:
There is no correct direction.
Comment #14 October 12th, 2005 at 6:56 am
Greg: The reason the complexity class naming conventions are such a mess is that they grew organically, like English. Would it be fair to describe your goal as that of “Frenchifying” complexity theory? ‘Cuz we don’t cotton to all them fancy rules where I come from. π
Comment #15 October 12th, 2005 at 9:23 am
Trackback ping
Comment #16 October 12th, 2005 at 9:53 am
Scott: That’s closer to the truth than you may have meant. Complexity classes need a Bourbaki reform. Bourbaki is the group that cleaned up the classification of complex simple Lie algebras.
Comment #17 October 14th, 2005 at 4:49 pm
Dr. Aaronson,
I’m late to this post, but there is goodness here.
First, congratulations on the choice to move the complexity zoo to a wiki format. I’ve thanked you in the past by email and I’m glad to see even further progress. Zookeeper, veteranarian and other handler jobs are easier when shared in a larger community format. Beside, your baby is now “all growed up”.
Second, I agree with Eldar. The wiki format allowing one topic per page is useful. Since that would require significant work, if you are serious about doing a change of this nature and need a hand with this, please contact me here:
http://www.jjbresearch.org/acs/blogs/optionsscalper/contact.aspx
Given the amount of information I’ve received from the zoo, I’d be happy to participate in “giving back” and donate some of my time to an effort of this nature.
Third, regarding the naming/taxonomy/ontology of the computational complexity classes, I don’t see them as any more chaotic or disorganized or improperly named than those used in biology or astronomy or other disciplines.
I think that a Bourbaki reform at this point may actually hinder rather than help this discipline at this point in it’s history. To follow on Andy Drucker’s point, there are relatively few axes that determine the classes. I think that there is still much to be learned and what will be discovered likely may impact any current choice for taxonomy or ontology. Those discoveries may even simplify the necessities for the current “class explosion”.
While DAML+OIL and OWL style ontologies (ala The Semantic Web) may help, I think that just moving forward with these steps to provide a useful public repository in the form of a wiki is beneficial.
Regards,
—O
p.s. Does anyone know if it is true that the “real” naming of complexity classes occurs in the wee hours of the morning after “complexity keggers”?
Comment #18 October 15th, 2005 at 8:39 pm
“Dr. Aaronson,”
Call me Scott.
“Given the amount of information I’ve received from the zoo, I’d be happy to participate in “giving back” and donate some of my time to an effort of this nature.”
Thanks — we’d be happy to take you up on your offer! You might want to contact John Stockton, the wiki manager, directly at jks@caltech.edu.
“I think that a Bourbaki reform at this point may actually hinder rather than help this discipline at this point in it’s history … I think that there is still much to be learned and what will be discovered likely may impact any current choice for taxonomy or ontology.”
Yes, I tend to agree with your position more than with Greg’s on this issue. (Possibly because I’m a computer scientist and Greg is a mathematician. π )
“p.s. Does anyone know if it is true that the “real” naming of complexity classes occurs in the wee hours of the morning after “complexity keggers”?”
Yes, it’s true.
Comment #19 October 17th, 2005 at 1:16 pm
I recognize the value of a chaotic frontier of research, whether it is computer science or mathematics. Order without chaos is a significant kind of stagnation in research, one famous historical example being invariant theory before Hilbert.
But chaos without order is another significant kind of stagnation. In building up science, the top floors may work better as a free-for-all. But it is very important to have a clean-up crew on the floors below, or else people will rummage at the top without making the building taller.
That is the service that Bourbaki ultimately performed for several fields of mathematics, for example representation theory. The Dynkin diagram classification of simple Lie algebras is a beautiful, disciplined thing that makes the exciting, undisciplined next stage possible. (Much of this next stage is known as quantum algebra.)
Indeed, the Zoo itself is a great Bourbaki-style clean-up operation in complexity theory, even if it was only partly intended that way.