Complexity Classes Meet Particle Physics

Juris Hartmanis is one of the founders of computational complexity, for which he was honored with the prestigious Turing Award. His theorems helped start the field, his PhD students are some of the best ever, and his conjectures have had huge influence on the development of the field. I have already posted about one of his wonderful conjectures on real-time computations.

Today I want to talk about a recent breakthrough result that proves that . I think that this terrific result, due to Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous, raises some interesting questions about the future of the field, and more generally of all of theory.

I still remember a talk that Juris gave at Yale University back in the mid 1970’s. At one point he put up a slide—no powerpoint then—with the following formula on it:

He pointed out that the ends of this chain were easily known to be different. He then smiled and said, therefore, at least one of the subset relations had to be proper. But which one? Was there just one that was proper? Or two? Or all three? This simple observation made a big impression on me. It’s too bad that over three decades later we have made no further insight into which one(s) is proper.

Back then, Yale computer science used the post-talk-food normal form. That is after the talk donuts were served to the audience and the speaker. Most places then and now use pre-talk-food normal form, but Yale was different. I always wondered why we were different, but it was Yale.

While we were eating our donuts one of my system colleagues said that he had an intuition about P=NP. A few of us perked up and asked what it was. He said he thought that they should be equal. We asked why? He said look: nondeterministic does not matter for finite state automata, does not matter for pushdown automata, and therefore why should it matter for Turing Machines? I liked this general analogy, but I pointed out that it does help for pushdown automata. Not all context free languages are accepted by a deterministic pushdown machine. He said never mind. Oh well.

The Complexity Classes

I have often thought that complexity classes could be viewed as our analog of particles in Physics. Really, I am not kidding. It is not April first.

Today there are over 200 known “fundamental” particles. See this for a short introduction. Not all particles are indivisible, some are made up of others. I am not a particle physics expert, so please forgive me ahead of time—no doubt I will say something wrong about particles.

The central thesis, however, that strikes me as an interesting one is:

Here are some of my reasons for this analogy:

Complexity classes are the basic objects that we study.

Complexity classes have properties. Instead of mass, spin, charge, and so on; we have our properties. Is it closed under complement? Does it have a complete set? Does the complete set, if it exists, have special properties such as random self-reduction? Is it low? Recall, that a complexity class is low for a complexity class , if with an oracle for is equal to . And so on.

Complexity classes sometimes are known to be different—unconditionally. For example, is not equal to .

Complexity classes sometimes are known to be the same. The recent result about is a perfect example of this behavior. Here two “particles” were known, but eventually were shown to be actually the same.

Complexity classes have a natural global mapping between them. For each class there is another class . This is a mapping from the classes to the classes. Of course there are some classes that are fixed points: is trivial, and was a big result.

So What?

One question you might ask is why is this a useful analogy? I like it because I think that the huge zoo of complexity classes is unlikely to be the fundamental ones. I like the analogy to particle physics more that the analogy to a zoo—with all due respect to the keepers of this valuable web resource: Scott Aaronson, Greg Kuperberg, and Christopher Granade.

I think that we should model our behavior closer to physics that to zoo’s. For example, the physics world is constantly searching for a reduction in the number of “fundamental particles”. We are doing the same. Every time two classes are proved the same, we have reduced the number of fundamental particles.

This analogy raises some interesting ideas. Forget for a moment the conventional wisdom on the complexity classes. What is the fewest distinct classes that we could have? For example, what possible worlds could exist if huge collapses happen? Then, I would like it because the world could become very simple, since there are only a few distinct classes.

On the other hand, what is the most complex world? I guess the obvious answer is that all known classes that are not yet proved to be the same are different. To me that seems like a pretty complex and unappealing situation. I would hope that this does not happen, but it could.

Open Problems

The co-mapping is a kind of symmetry between classes. Could this be like the matter and anti-matter symmetry of particle physics? Note it is known that for physics the symmetry is not perfect. The same seems to be true for our classes. For example, may behave differently, then

Where are the accelerators? Unfortunately, I cannot imagine how to build a multi-billion dollar machine that we could use to discover the structure of our fundamental particles. If we could that would be a great way to get more dollars flowing into theory. Any suggestions?

I think, in a sense, we are the accelerators. As we smash ideas together sometimes we discover the further structure of our fundamental particles—our complexity classes.