<p>The Complexity Zoo has a reference to that result in the description of the class <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#ampolylog">AM[polylog]</a>:</p>

<blockquote>
  <p>[…] <a href="http://qwiki.stanford.edu/index.php/Zooref#ss04">[SS04]</a> show that if AM[polylog] contains <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#conp">coNP</a>, then <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aE#eh">EH</a> collapses to <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#s2exppnp">S<sub>2</sub>-EXP•P<sup>NP</sup></a>. (<a href="http://qwiki.stanford.edu/index.php/Zooref#pv04">[PV04]</a> improved the collapse to <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#amexp">AM<sub>EXP</sub></a>.) </p>
</blockquote>

<p>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 <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#conppoly">coNP/poly</a> and <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#sfk">SF<sub><i>k</i></sub></a> (not for the easily scared, reader discretion is advised).</p>

CC BY-SA 2.5
2010-12-05T19:52:05.330Z
excellent. That class itself is quite scary.
Suresh Venkat
CC BY-SA 2.5
2010-12-05T21:43:21.953Z
Still, how is that a scandal?
Michaël Cadilhac
CC BY-SA 2.5
2010-12-05T23:26:44.153Z
@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
CC BY-SA 2.5
2010-12-06T01:10:33.310Z
This is one of the funniest problem-answer pair in TCS SE :P
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-06T07:10:04.293Z
At least untill we start discussing Robertson-Seymour lemmas on hairy animals with balls
Suresh Venkat
CC BY-SA 2.5
2010-12-05T19:37:15.613Z
2010-12-05T19:37:15.613Z
Tsuyoshi Ito
<p>This is a somewhat frivolous question that popped up in my head after reading the various responses to <a href="https://cstheory.stackexchange.com/questions/3566/whats-the-smallest-complexity-class-for-which-a-superlinear-circuit-bound-is-k">"What's the “smallest” complexity class for which a superlinear circuit bound is known?</a>". </p>

<p>Answers refer to $\mathsf{S_2 P}$, and when I looked at <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#s2p" rel="nofollow noreferrer">the zoo entry for it</a>, I discovered this: </p>

<blockquote>
  <p>$\mathsf{S_2-EXP•P^{NP}}$: Don't Ask</p>
  
  <p>One of the caged classes of the
  Complexity Zoo.</p>
  
  <p>Has been implicated in a collapse
  scandal involving $\mathsf{AM}[\text{polylog}]$, $\mathsf{coNP}$,
  and $\mathsf{EH}$</p>
</blockquote>

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

<cc.complexity-theory><complexity-classes>
"Caged" complexity classes ?
Suresh Venkat
# "Caged" complexity classes ?

(Asked by: username_0 on 2010-12-05)

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?](https://cstheory.stackexchange.com/questions/3566/whats-the-smallest-complexity-class-for-which-a-superlinear-circuit-bound-is-k)".

Answers refer to $\mathsf{S\_2 P}$, and when I looked at [the zoo entry for it](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#s2p), 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.

**Tags:** cc.complexity-theory, complexity-classes


---

## 1 answers

### Answer by username_1 on 2010-12-05. Score: 14 | Accepted answer

The Complexity Zoo has a reference to that result in the description of the class [AM[polylog]](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#ampolylog):

> […] [[SS04]](http://qwiki.stanford.edu/index.php/Zooref#ss04) show that if AM[polylog] contains [coNP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#conp), then [EH](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aE#eh) collapses to [S2-EXP•PNP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#s2exppnp). ([[PV04]](http://qwiki.stanford.edu/index.php/Zooref#pv04) improved the collapse to [AMEXP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#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](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#conppoly) and [SF*k*](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#sfk) (not for the easily scared, reader discretion is advised).

> **Comments:**
> **username_0**: excellent. That class itself is quite scary.  
> **username_2**: Still, how is that a scandal?  
> **username_1**: @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.  
> **username_3**: This is one of the funniest problem-answer pair in TCS SE :P  
> **username_0**: At least untill we start discussing Robertson-Seymour lemmas on hairy animals with balls  

---

