Oracle Separation Survey

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

1
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 2011 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 2011 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 2011 at 16:36

2 Answers

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

-

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 3, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9343022108078003, "perplexity_flag": "middle"}