11
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
14
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ excellent. That class itself is quite scary. $\endgroup$
    – Suresh Venkat
    Dec 5, 2010 at 19:52
  • 4
    $\begingroup$ Still, how is that a scandal? $\endgroup$
    – Michaël Cadilhac
    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$
    – Tsuyoshi Ito
    Dec 5, 2010 at 23:26
  • 2
    $\begingroup$ This is one of the funniest problem-answer pair in TCS SE :P $\endgroup$
    – Hsien-Chih Chang 張顯之
    Dec 6, 2010 at 1:10
  • 4
    $\begingroup$ At least untill we start discussing Robertson-Seymour lemmas on hairy animals with balls $\endgroup$
    – Suresh Venkat
    Dec 6, 2010 at 7:10

Your Answer

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

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