Is there a survey (or a website) somewhere that lists all known separation results?

I.e. it has a list of triples:

$$ (C_1, C_2, A)$$


1. We do not know if $C_1 = C_2$
2. We know that $C_1^A = C_2^A$ or $C_1^A \neq C_A^A$

I.e. I'm looking for a big list, for classes like:

L vs P. P vs NP. BPP vs NEXP. etc ...

  • 1
    $\begingroup$ I second JDH's suggestion of the Complexity Zoo, though, from what I can tell, it will require you to compile the answers yourself by going through all the 495 classes listed there. On the plus side, I would tend to trust the zoo to have even the latest results, and the zookeepers are very good with providing references for everything. The site was created specifically because few people can confidently remember such long lists of separation results. $\endgroup$ – Thierry Zell Sep 18 '11 at 14:43
  • $\begingroup$ By the way, I'm sure there must be surveys too. They will be more reader-friendly, but less comprehensive, by definition. In the long run, you probably want to look at both. $\endgroup$ – Thierry Zell Sep 18 '11 at 14:46
  • $\begingroup$ Is there a general definition, given a class $C$ of languages, what the relativized class $C^A$ means for oracle $A$? This notation seems confusing to me. $\endgroup$ – David Harris Sep 18 '11 at 16:36

The Complexity Zoo compiles a huge amount of the information you want, if not exactly in the form you request.


The Complexity Zoology gives you exactly what you are looking for.


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.