Classes de complexidade "em gaiola"?

8

Esta é uma pergunta um tanto frívola que surgiu na minha cabeça depois de ler as várias respostas para "Qual é a menor classe de complexidade para a qual um circuito superlinear é conhecido? ".

As respostas se referem a e, quando olhei para a entrada do zoológico , descobri o seguinte:S2P

: Não pergunteS2EXPPNP

Uma das classes engaioladas do Zoo Complexity.

Tem sido implicada num escândalo envolvendo colapso , c o N P , e E HAM[polylog]coNPEH

Então agora estou intrigado. O que é uma classe de complexidade enjaulada e qual é o escândalo suculento aqui :)? O zoológico não tem referências para esclarecer.

Suresh Venkat
fonte

Respostas:

11

O Zoológico de Complexidade tem uma referência a esse resultado na descrição da classe AM [polylog] :

[…] [SS04] mostra que se AM [polilog] contém coNP , então EH entra em colapso para S 2 -EXP • P NP . ( [PV04] melhorou o colapso para AM EXP .)

No Zoológico de Complexidade, uma classe ou uma instrução é enjaulada quando parece muito assustadora. Exemplos de instruções em gaiola podem ser encontrados nas descrições de coNP / poly e SF k (não para os que se assustam facilmente, recomenda-se a discrição do leitor).

Tsuyoshi Ito
fonte
2
excelente. Essa aula em si é bastante assustadora.
Suresh Venkat
3
Ainda assim, como isso é um escândalo?
Michaël Cadilhac
@ Michaël: Um colapso é uma coisa ruim por definição . Consulte cstheory.stackexchange.com/questions/3111/… . Embora esse artigo não contenha a palavra "escândalo", você entenderá.
Tsuyoshi Ito
1
Este é um dos mais divertidos par problema-resposta em TCS SE: P
Hsien-Chih Chang張顯之
4
Pelo menos até o hotel começar a discutir Robertson-Seymour lemas em animais peludos com bolas
Suresh Venkat