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

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

share|improve this question
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. –  Thierry Zell Sep 18 '11 at 14:43
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. –  Thierry Zell Sep 18 '11 at 14:46
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. –  David Harris Sep 18 '11 at 16:36
add comment

2 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer


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.