show/hide this revision's text 2 edited tags
show/hide this revision's text 1

Survey on Structural Complexity

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!