# "Caged" complexity classes ?

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.

## 1 Answer

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 S2-EXP•PNP. ([PV04] improved the collapse to AMEXP.)

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 SFk (not for the easily scared, reader discretion is advised).

• excellent. That class itself is quite scary. Dec 5 '10 at 19:52
• Still, how is that a scandal? Dec 5 '10 at 21:43
• @Michaël: A collapse is a bad thing by definition. See cstheory.stackexchange.com/questions/3111/…. Although that article does not contain the word “scandal,” you will get the idea. Dec 5 '10 at 23:26
• This is one of the funniest problem-answer pair in TCS SE :P Dec 6 '10 at 1:10
• At least untill we start discussing Robertson-Seymour lemmas on hairy animals with balls Dec 6 '10 at 7:10