"Caged" complexity classes ?

Question

This is a somewhat frivolous question that popped up in my head after reading the various responses to "What's the “smallest” complexity class for which a superlinear circuit bound is known?".

Answers refer to $\mathsf{S_2 P}$, and when I looked at the zoo entry for it, I discovered this:

$\mathsf{S_2-EXP•P^{NP}}$: Don't Ask

One of the caged classes of the Complexity Zoo.

Has been implicated in a collapse scandal involving $\mathsf{AM}[\text{polylog}]$, $\mathsf{coNP}$, and $\mathsf{EH}$

So now I'm intrigued. What's a caged complexity class, and what's the juicy scandal here :) ? The zoo has no references to clarify.

score 14 · Accepted Answer · answered Dec 05 '10 at 19:37

14

The Complexity Zoo has a reference to that result in the description of the class AM[polylog]:

[…] [SS04] show that if AM[polylog] contains coNP, then EH collapses to S₂-EXP•P^NP. ([PV04] improved the collapse to AM_EXP.)

In the Complexity Zoo, a class or a statement is caged when it looks very scary. Examples of caged statements can be found in the descriptions of coNP/poly and SF_k (not for the easily scared, reader discretion is advised).

answered Dec 05 '10 at 19:37

Tsuyoshi Ito

16,466
2
55
106

2

excellent. That class itself is quite scary. – Suresh Venkat Dec 05 '10 at 19:52
4

Still, how is that a scandal? – Michaël Cadilhac Dec 05 '10 at 21:43
@Michaël: A collapse is a bad thing by definition. See http://cstheory.stackexchange.com/questions/3111/funny-tcs-related-papers-etc/3112#3112. Although that article does not contain the word “scandal,” you will get the idea. – Tsuyoshi Ito Dec 05 '10 at 23:26
2

This is one of the funniest problem-answer pair in TCS SE :P – Hsien-Chih Chang 張顯之 Dec 06 '10 at 01:10
4

At least untill we start discussing Robertson-Seymour lemmas on hairy animals with balls – Suresh Venkat Dec 06 '10 at 07:10

"Caged" complexity classes ?

1 Answers1