Se derrumba bajo el supuesto de que

Se sabe que si , la jerarquía polinómica se colapsa en y .N P ⊆ P / P o l y Σ P 2 M A = A $NP\subseteq P/Poly$$\Sigma_2^{P}$$MA = AM$

¿Cuáles son los colapsos más fuertes que suceden si ?$NEXP\subseteq P/Poly$

Creo que el más fuerte es que $NEXP = MA$ . Esto fue demostrado por Impagliazzo Kabanets y Wigderson.

Ver https://scholar.google.com/scholar?cluster=17275091615053693892&hl=es&as_sdt=0,5&sciodt=0,5

También me interesaría saber de colapsos más fuertes que este.

Editar (8/24): OK, pensé en un colapso potencialmente más fuerte, que esencialmente se desprende de las pruebas del documento vinculado anterior. Debido a que N E X P ⊂ P / p o l y implica N E X P = E X P (ver el enlace anterior), y E X P está cerrado bajo el complemento, también tenemos N E X P cerrado bajo el complemento y, por lo tanto, N E X P = M A ∩ c o M $NEXP \subset P/poly$$NEXP = EXP$$EXP$$NEXP$$NEXP = MA \cap coMA$, que es un poco más fuerte. De hecho, la hipótesis implica que para cualquier lenguaje N E X P , se puede usar una sola cadena testigo w n en el protocolo MA correspondiente para todas las instancias SÍ de cualquier longitud dada n , por lo que también N E X P = O M A ∩ c o O M A (donde O M A = "MA inconsciente", vea Fortnow-Santhanam-me http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&rep=rep1&type=pdf$NEXP$$w_n$$n$$NEXP = OMA \cap coOMA$$OMA$) Estas propiedades adicionales, aunque técnicas, podrían resultar útiles en algunos argumentos de límite inferior del circuito.

Edición 2: Parece que Andrew Morgan ya resaltó esto. Whoops :)

Suceden muchas cosas divertidas. La mayoría de las que conozco comienzan con el artículo de IKW . Allí, se muestra el colapso $\textrm{NEXP} = \textrm{MA}$ , y (creo) es el colapso literal más fuerte de las clases de complejidad que conocemos. Sin embargo, hay otros tipos de "colapsos" que creo que deberían señalarse.

Lo más importante, creo, es la propiedad del "testigo sucinto universal" (también del documento de IKW). Por un lado, le brinda una herramienta de la cual muchos de los otros colapsos son consecuencias directas; para otro, los límites inferiores del circuito reciente (por ejemplo, aquí y aquí ) para $\textsf{NEXP}$ explotan esta conexión. En pocas palabras, la propiedad dice que, para cada $\textsf{NEXP}$ lenguaje $L$ , y cualquier $\textsf{NEXP}$ -máquinas $M$ decidir $L$ , cada $x \in L$ tiene una sucinta descriptible testigo acuerdo con $M$ . Formalmente, hay un polinomio $p$ dependiendo de$M$ para que por cada$x \in L$ , haya un circuito$C_x$ de tamaño$p(|x|)$ modo que la tabla de verdad de$C_x$ sea ​​una secuencia de opciones no deterministas para$M$ que conducen a la aceptación en la entrada$x$ .

La brevedad de los testigos resulta útil, ya que puede derivar directamente muchos de los otros colapsos. Por ejemplo, se sigue trivialmente que $\textsf{NEXP} = \textsf{coNEXP} = \textsf{EXP}$ . Por ejemplo, supongamos que $L$ es en $\textsf{NEXP}$ a través de un $\textsf{NEXP}$ -máquinas $M$ . La propiedad de testigo sucinto dice que hay un polinomio $p$ para que $M$ tenga testigos sucintos de tamaño $p$ . Entonces podemos decidir $L$ en $\textsf{EXP}$ mediante, en la entrada $x$ , forzando a todos los circuitos de tamaño bruto como máximo $p(|x|)$ y comprobar si codifican una secuencia de opciones que conducen a que$M$ acepte en la entrada$x$ . Puede combinar esto con el resultado (previamente conocido a través de pruebas interactivas) que$\textsf{EXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{EXP} = \textsf{MA}$ para concluir$\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{NEXP} = \textsf{MA}$ .

Vale la pena enfatizar que podemos elegir $M$ y, por lo tanto, la forma de los testigos. Por ejemplo, puede concluir de " $\textsf{NEXP}$ tiene testigos sucintos universales" que $\textsf{NEXP} = \textsf{OMA} = \textsf{co-OMA}$ . Aquí $\textsf{OMA}$ es "MA inconsciente", lo que significa que hay un Merlín honesto que depende solo de la longitud de entrada. Es fácil ver que $\textsf{OMA} \subseteq \textsf{P}/\textrm{poly}$ , así que básicamente esto es solo una forma normal de cómo se $\textsf{NEXP}$ lenguajes NEXP en $\textsf{P}/\textrm{poly}$ bajo el supuesto de que $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$ in the first place. Here's one way to see the collapse to $\textsf{OMA}$:

Para un lenguaje $L \in \mathsf{NEXP}$ decidido por una máquina $M$ , construya una máquina $\mathsf{NEXP}$$M'$ como sigue. Vea la entrada de $n$ bits como un número $N$ entre $1$ y $2^n$ . Por cada $x$ de longitud $n$ , adivine un testigo $w_x$ y ejecute $M(x,w_x)$ para verificarlo. $M'(N)$acepta si y solo si $M$ acepta al menos $N$ valores de $x$ . Las conjeturas se organizan de tal manera que una descripción sucinta de un testigo para $M'$ es un circuito $C$ que calcula el mapa $(x,i) \mapsto$ el bit $i$ -ésimo de $w_x$ . Ahora suponga que $N$ es precisamente el número de cadenas en $L$ con una longitud $n$ . Entonces testigos sucintas para $M'$ en la entrada $N$ son circuitos que simultáneamente codifican todo de$M$'s witnesses for length-$n$ inputs. In particular, if $M'$ has succinct witnesses, then all of $M$'s witnesses can be simultaneously described by the same circuit.

To complete the claim, we'll recall that $\textsf{NEXP} = \textsf{PCP}[\textrm{poly}, \textrm{poly}]$. Letting $M$ be the machine which guesses the PCP and then deterministically simulates the verifier, the above paragraph tells us the existence of simultaneously succinctly describable PCPs for every language in $\textsf{NEXP}$. So now to get $\textsf{NEXP} = \textsf{OMA}$, we have Merlin send the succinct description of the PCPs for all inputs of the current input length, which Arthur can check by just plugging in his input and then running the PCP verifier.

[Thanks to Cody Murray for pointing out the trick of using the input to count the number of strings in $L$. Previously I had $M'$ use that if $\mathsf{NEXP}\subseteq\mathsf{P/poly}$ then $\mathsf{NEXP}=\mathsf{EXP}$ to write down the truth table of $L$, but Cody's strategy is more elegant.]

As a final note, while technically implied by $\textsf{NEXP}=\textsf{MA}$, the collapse $\textsf{NEXP}=\textsf{PSPACE}$ has another interesting implication. It's known that $\textsf{PSPACE}$ has a complete language which is both downward self-reducible as well as random self-reducible. Ordinarily, all such languages sit inside $\textsf{PSPACE}$ and so we shouldn't hope to say (unconditionally) that $\textsf{NEXP}$ has such a complete language as long as we hope that $\textsf{NEXP} \ne \textsf{PSPACE}$. However, if $\textsf{NEXP} = \textsf{PSPACE}$, then $\textsf{NEXP}$ does have such complete languages. A similar statement (replacing $\textsf{NEXP}$ by $\textsf{EXP}$) was used by Impagliazzo and Wigderson to conclude a sort of "derandomization dichotomy" for $\textsf{BPP}$ in relation to $\textsf{EXP}$, so it may be useful in discovering other consequences of $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$.