8
$\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.

$\endgroup$
11
$\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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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