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 1


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

  • 2
    $\begingroup$ excellent. That class itself is quite scary. $\endgroup$ Commented Dec 5, 2010 at 19:52
  • 4
    $\begingroup$ Still, how is that a scandal? $\endgroup$ Commented Dec 5, 2010 at 21:43
  • $\begingroup$ @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. $\endgroup$ Commented Dec 5, 2010 at 23:26
  • 2
    $\begingroup$ This is one of the funniest problem-answer pair in TCS SE :P $\endgroup$ Commented Dec 6, 2010 at 1:10
  • 4
    $\begingroup$ At least untill we start discussing Robertson-Seymour lemmas on hairy animals with balls $\endgroup$ Commented Dec 6, 2010 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.