4
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 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
    Commented Sep 7, 2011 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
    Commented Sep 7, 2011 at 15:37
  • 1
    $\begingroup$ related question on cstheory: cstheory.stackexchange.com/questions/811/… $\endgroup$
    – Kaveh
    Commented Sep 8, 2011 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
    Commented Sep 8, 2011 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
    Commented Sep 12, 2011 at 7:33

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .