2
$\begingroup$

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)$$

where

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

Improve this question
$\endgroup$
3
  • 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
    Commented Sep 18, 2011 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
    Commented Sep 18, 2011 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
    Commented Sep 18, 2011 at 16:36

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

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