In the 2011 Complexity proceedings
there are three papers that analyze complexity classes, Ryan Williams' great paper on ACC, Russell Impagliazzo's paper on average versus worst case for NP and a Hartmut Klauck's paper on AM in communication complexity. That's the complexity conference. At STOC
, there was only the Aaronson-Arkhipov paper on linear optics.
Complexity classes capture important aspects of problems based on how they can use various resources. The complexity zoo
has nearly 500 classes. Many of the greatest theorems in theoretical computer science relate classes like NPSPACE = PSPACE, NL = co-NL, PH ⊆ P#P
, IP = PSPACE, NP = PCP(log n,1), SL = L, NEXP not in ACC and many others. The most important open question in our field (and maybe any field) is the relationships of the classes P and NP.
So why do we see so few papers about complexity classes these days? We are victims of our own successes and failures. We have succeeded in classifying and relating most of the connections between classes where we don't have relativizable counterexamples and have failed, outside of interactive proofs, to develop many tools that let us get around relativization and other barriers.
So here we sit, still putting out the occasional paper on complexity classes but mostly hitting a wall. Occasionally we see a nice breakthrough like Ryan's paper but mostly we are just clawing at that wall waiting for someone to create a wrecking ball so we can make real progress.
Posted By Lance Fortnow to Computational Complexity
at 11/27/2011 05:49:00 AM