Alot of the proofs I've been recently reading:

IP / PSpace / MIP / NEXP / randomized reductions

have a certain flavour involving proofs showing equivalence/relation between various complexity classes. It turns out this field is called "structural complexity."

Is there a good survey of all known results in structural complexity? [Right now, all I have is a set of papers by Goldwasser / Sipser / Fortnow / ... from the late 80s early 90s].

[I'm interested in a survey that lists facts like:

IP = PSpace MIP = NEXP IP = AM M^O = MIP MIP has interactive zero-knolwedge proofs for for NP w/o needing any crypto assumptions. ....


  • 1
    $\begingroup$ Doesn't Sipser's book "Introduction to the Theory of Computation" have some nice tables breaking down what's known? I don't have my copy on me, but I remember him devoting lots of time to P, NP, and other classes for both time complexity and space complexity. Admittedly, that might be a bit out of date and probably won't contain all the fine divisions, but it seems a good place to start. $\endgroup$ – David White Sep 7 '11 at 15:35
  • $\begingroup$ Intro level textbooks cover thigns like P, NP, BPP, L, NL, RL, coNL, space complexit hierarcy, time hiearchy. However, there's alot of work on Interactive Proofs / Zero knowledge proof of knowedge that I don't see in these books. $\endgroup$ – structural complexity Sep 7 '11 at 15:37
  • 1
    $\begingroup$ related question on cstheory: cstheory.stackexchange.com/questions/811/… $\endgroup$ – Kaveh Sep 8 '11 at 2:26
  • 2
    $\begingroup$ ps: I am not sure if the results you want to know about are part of structural complexity theory: en.wikipedia.org/wiki/Structural_complexity_theory $\endgroup$ – Kaveh Sep 8 '11 at 2:27
  • 3
    $\begingroup$ A book that needs to be updated, but was perfect at the time, was Structural Complexity by Balcazar, Diaz and Gabarro: books.google.com/books/about/… $\endgroup$ – Suresh Venkat Sep 12 '11 at 7:33

The best reference for relationships between complexity classes is the Complexity Zoo. It also includes useful sections such as the Petting Zoo and the Special Exhibit of quantum classes. Perhaps because the Zoo is so extensive (nearly 500 entries currently), new classes are added regularly, while many old classes have yet to be added, no-one has written a comprehensive survey.

Some of the interesting structure of the lattice of classes is captured by descriptive complexity, which relates many of the main classes to fragments of logic.

Recent textbooks like Arora/Barak, Kozen, and Sipser do cover many of the "standard" relationships you mention.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.