Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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. ....

Thanks!

share|improve this question
    
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. –  David White Sep 7 '11 at 15:35
    
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. –  structural complexity Sep 7 '11 at 15:37
    
(I'm certain said authors of textbooks are experts in the arena; the problem is I can;t find any survey type exposition of the topics.) –  structural complexity Sep 7 '11 at 15:38
2  
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 –  Kaveh Sep 8 '11 at 2:27
2  
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/… –  Suresh Venkat Sep 12 '11 at 7:33
show 1 more comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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