|
2 |
edited tags
|
||
|
1 |
|
||
Survey on Structural ComplexityAlot 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!
|
||||

