¿Clases de complejidad "enjauladas"?

8

Esta es una pregunta algo frívola que surgió en mi cabeza después de leer las diversas respuestas a "¿Cuál es la clase de complejidad" más pequeña "para la que se conoce un circuito superlineal? ".

Las respuestas se refieren a , y cuando miré la entrada del zoológico , descubrí esto:S2P

: No preguntarS2EXPPNP

Una de las clases enjauladas del complejo zoológico.

Ha sido implicado en un escándalo de colapso que involucra a , c o N P y E HAM[polylog]coNPEH

Entonces ahora estoy intrigado. ¿Qué es una clase de complejidad enjaulada y cuál es el jugoso escándalo aquí :)? El zoológico no tiene referencias para aclarar.

Suresh Venkat
fuente

Respuestas:

11

Complexity Zoo tiene una referencia a ese resultado en la descripción de la clase AM [polylog] :

[…] [SS04] muestra que si AM [polylog] contiene coNP , EH colapsa a S 2 -EXP • P NP . ( [PV04] mejoró el colapso a AM EXP .)

En Complexity Zoo, una clase o una declaración se enjaula cuando parece muy aterrador. Se pueden encontrar ejemplos de declaraciones enjauladas en las descripciones de coNP / poly y SF k (no para los que se asustan fácilmente, se recomienda la discreción del lector).

Tsuyoshi Ito
fuente
2
excelente. Esa clase en sí es bastante aterradora.
Suresh Venkat
3
Aún así, ¿cómo es eso un escándalo?
Michaël Cadilhac
@ Michaël: Un colapso es algo malo por definición . Ver cstheory.stackexchange.com/questions/3111/… . Aunque ese artículo no contiene la palabra "escándalo", se dará cuenta de la idea.
Tsuyoshi Ito
1
Este es uno de los pares más divertidos de problema-respuesta en TCS SE: P
Hsien-Chih Chang 張顯 之
44
Al menos hasta que empecemos a hablar sobre los lemas de Robertson-Seymour sobre animales peludos con pelotas
Suresh Venkat