<p>A whole lot of fun things happen. Most of the ones I know of start with the <a href="https://scholar.google.com/scholar?cluster=17275091615053693892&amp;hl=en&amp;as_sdt=0,5&amp;sciodt=0,5" rel="noreferrer">IKW paper</a>. There, the collapse <span class="math-container">$\textrm{NEXP} = \textrm{MA}$</span> is shown, and (I think) is the strongest literal collapse of complexity classes that we know of. There are other sorts of &quot;collapses&quot; though that I think should be pointed out.</p>
<p>Most importantly, I think, is the &quot;universal succinct witness&quot; property (also from the IKW paper). For one, it gives you a tool from which many of the other collapses are straightforward consequences; for another, the recent circuit lower bounds (eg <a href="http://dl.acm.org/citation.cfm?doid=2591796.2591858" rel="noreferrer">here</a> and <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.413.2008" rel="noreferrer">here</a>) for <span class="math-container">$\textsf{NEXP}$</span> exploit this connection. Briefly, the property says that, for every <span class="math-container">$\textsf{NEXP}$</span> language <span class="math-container">$L$</span>, and any <span class="math-container">$\textsf{NEXP}$</span>-machine <span class="math-container">$M$</span> deciding <span class="math-container">$L$</span>, every <span class="math-container">$x \in L$</span> has a <em>succinctly describable</em> witness according to <span class="math-container">$M$</span>. Formally, there is a polynomial <span class="math-container">$p$</span> depending on <span class="math-container">$M$</span> so that for every <span class="math-container">$x \in L$</span>, there is a circuit <span class="math-container">$C_x$</span> of size <span class="math-container">$p(|x|)$</span> so that the truth table of <span class="math-container">$C_x$</span> is a sequence of nondeterministic choices for <span class="math-container">$M$</span> that lead to acceptance on input <span class="math-container">$x$</span>.</p>
<p>The succinctness of the witnesses comes in handy, because you can straightforwardly rederive a lot of the other collapses from it. For instance, it follows trivially that <span class="math-container">$\textsf{NEXP} = \textsf{coNEXP} = \textsf{EXP}$</span>. For example, suppose <span class="math-container">$L$</span> is in <span class="math-container">$\textsf{NEXP}$</span> via a <span class="math-container">$\textsf{NEXP}$</span>-machine <span class="math-container">$M$</span>. The succinct-witness property says there's a polynomial <span class="math-container">$p$</span> so that <span class="math-container">$M$</span> has succinct witnesses of size <span class="math-container">$p$</span>. We can then decide <span class="math-container">$L$</span> in <span class="math-container">$\textsf{EXP}$</span> by, on input <span class="math-container">$x$</span>, brute-forcing all the circuits of size at most <span class="math-container">$p(|x|)$</span>, and checking whether they encode a sequence of choices that lead to <span class="math-container">$M$</span> accepting on input <span class="math-container">$x$</span>. You can combine this with the (previously known via interactive proofs) result that <span class="math-container">$\textsf{EXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{EXP} = \textsf{MA}$</span> to conclude <span class="math-container">$\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{NEXP} = \textsf{MA}$</span>.</p>
<p>It's worth emphasizing that we get to pick <span class="math-container">$M$</span> and hence the form of the witnesses. For example, you can actually conclude from &quot;<span class="math-container">$\textsf{NEXP}$</span> has universal succinct witnesses&quot; that <span class="math-container">$\textsf{NEXP} = \textsf{OMA} = \textsf{co-OMA}$</span>. Here <span class="math-container">$\textsf{OMA}$</span> is &quot;oblivious-MA&quot;, meaning that there is an honest Merlin which depends only on the input length.
It's easy to see that <span class="math-container">$\textsf{OMA} \subseteq \textsf{P}/\textrm{poly}$</span>, so basically this is just giving a normal form for how <span class="math-container">$\textsf{NEXP}$</span> languages are computed in <span class="math-container">$\textsf{P}/\textrm{poly}$</span> under the assumption that <span class="math-container">$\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$</span> in the first place.
Here's one way to see the collapse to <span class="math-container">$\textsf{OMA}$</span>:</p>
<blockquote>
<p>For a language <span class="math-container">$L \in \mathsf{NEXP}$</span> decided by a machine <span class="math-container">$M$</span>, construct a <span class="math-container">$\mathsf{NEXP}$</span> machine <span class="math-container">$M'$</span> as follows. View the <span class="math-container">$n$</span>-bit input as a number <span class="math-container">$N$</span> between <span class="math-container">$1$</span> and <span class="math-container">$2^n$</span>. For every <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>, guess a witness <span class="math-container">$w_x$</span> and run <span class="math-container">$M(x,w_x)$</span> to verify it. <span class="math-container">$M'(N)$</span> accepts if and only if <span class="math-container">$M$</span> accepts for at least <span class="math-container">$N$</span> values of <span class="math-container">$x$</span>. The guesses are arranged such that a succinct description of a witness for <span class="math-container">$M'$</span> is a circuit <span class="math-container">$C$</span> which computes the map <span class="math-container">$(x,i) \mapsto$</span> the <span class="math-container">$i$</span>-th bit of <span class="math-container">$w_x$</span>. Now suppose that <span class="math-container">$N$</span> is precisely the number of strings in <span class="math-container">$L$</span> at length <span class="math-container">$n$</span>. Then succinct witnesses for <span class="math-container">$M'$</span> on input <span class="math-container">$N$</span> are circuits that simultaneously encode <em>all</em> of <span class="math-container">$M$</span>'s witnesses for length-<span class="math-container">$n$</span> inputs. In particular, if <span class="math-container">$M'$</span> has succinct witnesses, then all of <span class="math-container">$M$</span>'s witnesses can be simultaneously described by the same circuit.</p>
<p>To complete the claim, we'll recall that <span class="math-container">$\textsf{NEXP} = \textsf{PCP}[\textrm{poly}, \textrm{poly}]$</span>. Letting <span class="math-container">$M$</span> 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 <span class="math-container">$\textsf{NEXP}$</span>. So now to get <span class="math-container">$\textsf{NEXP} = \textsf{OMA}$</span>, 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.</p>
</blockquote>
<p>[Thanks to Cody Murray for pointing out the trick of using the input to count the number of strings in <span class="math-container">$L$</span>. Previously I had <span class="math-container">$M'$</span> use that if <span class="math-container">$\mathsf{NEXP}\subseteq\mathsf{P/poly}$</span> then <span class="math-container">$\mathsf{NEXP}=\mathsf{EXP}$</span> to write down the truth table of <span class="math-container">$L$</span>, but Cody's strategy is more elegant.]</p>
<p>As a final note, while technically implied by <span class="math-container">$\textsf{NEXP}=\textsf{MA}$</span>, the collapse <span class="math-container">$\textsf{NEXP}=\textsf{PSPACE}$</span> has another interesting implication. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.9919" rel="noreferrer">It's known</a> that <span class="math-container">$\textsf{PSPACE}$</span> has a complete language which is both downward self-reducible as well as random self-reducible. Ordinarily, all such languages sit inside <span class="math-container">$\textsf{PSPACE}$</span> and so we shouldn't hope to say (unconditionally) that <span class="math-container">$\textsf{NEXP}$</span> has such a complete language as long as we hope that <span class="math-container">$\textsf{NEXP} \ne \textsf{PSPACE}$</span>. However, if <span class="math-container">$\textsf{NEXP} = \textsf{PSPACE}$</span>, then <span class="math-container">$\textsf{NEXP}$</span> <em>does</em> have such complete languages. A similar statement (replacing <span class="math-container">$\textsf{NEXP}$</span> by <span class="math-container">$\textsf{EXP}$</span>) was <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.4807" rel="noreferrer">used by Impagliazzo and Wigderson</a> to conclude a sort of &quot;derandomization dichotomy&quot; for <span class="math-container">$\textsf{BPP}$</span> in relation to <span class="math-container">$\textsf{EXP}$</span>, so it may be useful in discovering other consequences of <span class="math-container">$\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$</span>.</p>

CC BY-SA 3.0
2016-08-08T11:25:39.820Z
BTW, don't trust citeseer to have the most recent (or even the best-rendered) versions of my papers. Here's better :) http://web.stanford.edu/~rrwill/projects.html
Ryan Williams
CC BY-SA 3.0
2016-08-08T16:33:02.267Z
Thanks for the advice! I'll keep it in mind for the future (and that it likely applies to other authors as well).
Andrew Morgan
CC BY-SA 4.0
2016-07-20T17:27:55.063Z
2018-11-28T18:24:18.943Z
2020-06-17T09:38:08.363Z
Andrew Morgan
<p>I believe the strongest is that $NEXP = MA$. This was proved by Impagliazzo Kabanets and Wigderson.</p>

<p>See <a href="https://scholar.google.com/scholar?cluster=17275091615053693892&amp;hl=en&amp;as_sdt=0,5&amp;sciodt=0,5">https://scholar.google.com/scholar?cluster=17275091615053693892&amp;hl=en&amp;as_sdt=0,5&amp;sciodt=0,5</a></p>

<p>I'd be also interested to know of any stronger collapses than this.</p>

<p>Edit (8/24): OK, I thought of some potentially stronger collapse, which essentially follows from the proofs of the above linked paper. Because $NEXP \subset P/poly$ implies $NEXP = EXP$ (see the above link), and $EXP$ is closed under complement, we also have $NEXP$ closed under complement and therefore $NEXP = MA \cap coMA$, which is a little stronger. Indeed, the hypothesis implies that for any $NEXP$ language, a <em>single</em> witness string $w_n$ can be used in the corresponding MA protocol for all YES-instances of any given length $n$, so also $NEXP = OMA \cap coOMA$ (where $OMA$ = "Oblivious MA", see Fortnow-Santhanam-me <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&amp;rep=rep1&amp;type=pdf">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&amp;rep=rep1&amp;type=pdf</a>). These extra properties, while technical, could prove to be useful in some circuit lower bound argument.</p>

<p>Edit 2: Looks like Andrew Morgan highlighted this already. Whoops :)</p>

CC BY-SA 3.0
2016-07-20T14:16:26.817Z
2016-08-24T20:37:34.747Z
2016-08-24T20:37:34.747Z
Ryan Williams
<p>It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma_2^{P}$ and $MA = AM$. </p>

<p>What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$? </p>

<circuit-complexity><complexity>
Collapses under the assumption that $NEXP\subseteq P/Poly$
Springberg
# Collapses under the assumption that $NEXP\subseteq P/Poly$

(Asked by: username_0 on 2016-07-20)

It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma\_2^{P}$ and $MA = AM$.

What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$?

**Tags:** circuit-complexity, complexity

---

## 2 answers

### Answer by username_2 on 2016-07-20. Score: 13 | Accepted answer

I believe the strongest is that $NEXP = MA$. This was proved by Impagliazzo Kabanets and Wigderson.

See <https://scholar.google.com/scholar?cluster=17275091615053693892&hl=en&as_sdt=0,5&sciodt=0,5>

I'd be also interested to know of any stronger collapses than this.

Edit (8/24): OK, I thought of some potentially stronger collapse, which essentially follows from the proofs of the above linked paper. Because $NEXP \subset P/poly$ implies $NEXP = EXP$ (see the above link), and $EXP$ is closed under complement, we also have $NEXP$ closed under complement and therefore $NEXP = MA \cap coMA$, which is a little stronger. Indeed, the hypothesis implies that for any $NEXP$ language, a *single* witness string $w\_n$ can be used in the corresponding MA protocol for all YES-instances of any given length $n$, so also $NEXP = OMA \cap coOMA$ (where $OMA$ = "Oblivious MA", see Fortnow-Santhanam-me <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&rep=rep1&type=pdf>). These extra properties, while technical, could prove to be useful in some circuit lower bound argument.

Edit 2: Looks like Andrew Morgan highlighted this already. Whoops :)


---

### Answer by username_1 on 2016-07-20. Score: 15

A whole lot of fun things happen. Most of the ones I know of start with the [IKW paper](https://scholar.google.com/scholar?cluster=17275091615053693892&hl=en&as_sdt=0,5&sciodt=0,5). There, the collapse $\textrm{NEXP} = \textrm{MA}$ is shown, and (I think) is the strongest literal collapse of complexity classes that we know of. There are other sorts of "collapses" though that I think should be pointed out.

Most importantly, I think, is the "universal succinct witness" property (also from the IKW paper). For one, it gives you a tool from which many of the other collapses are straightforward consequences; for another, the recent circuit lower bounds (eg [here](http://dl.acm.org/citation.cfm?doid=2591796.2591858) and [here](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.413.2008)) for $\textsf{NEXP}$ exploit this connection. Briefly, the property says that, for every $\textsf{NEXP}$ language $L$, and any $\textsf{NEXP}$-machine $M$ deciding $L$, every $x \in L$ has a *succinctly describable* witness according to $M$. Formally, there is a polynomial $p$ depending on $M$ so that for every $x \in L$, there is a circuit $C\_x$ of size $p(|x|)$ so that the truth table of $C\_x$ is a sequence of nondeterministic choices for $M$ that lead to acceptance on input $x$.

The succinctness of the witnesses comes in handy, because you can straightforwardly rederive a lot of the other collapses from it. For instance, it follows trivially that $\textsf{NEXP} = \textsf{coNEXP} = \textsf{EXP}$. For example, suppose $L$ is in $\textsf{NEXP}$ via a $\textsf{NEXP}$-machine $M$. The succinct-witness property says there's a polynomial $p$ so that $M$ has succinct witnesses of size $p$. We can then decide $L$ in $\textsf{EXP}$ by, on input $x$, brute-forcing all the circuits of size at most $p(|x|)$, and checking whether they encode a sequence of choices that lead to $M$ accepting on input $x$. You can combine this with the (previously known via interactive proofs) result that $\textsf{EXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{EXP} = \textsf{MA}$ to conclude $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{NEXP} = \textsf{MA}$.

It's worth emphasizing that we get to pick $M$ and hence the form of the witnesses. For example, you can actually conclude from "$\textsf{NEXP}$ has universal succinct witnesses" that $\textsf{NEXP} = \textsf{OMA} = \textsf{co-OMA}$. Here $\textsf{OMA}$ is "oblivious-MA", meaning that there is an honest Merlin which depends only on the input length.
It's easy to see that $\textsf{OMA} \subseteq \textsf{P}/\textrm{poly}$, so basically this is just giving a normal form for how $\textsf{NEXP}$ languages are computed in $\textsf{P}/\textrm{poly}$ under the assumption that $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$ in the first place.
Here's one way to see the collapse to $\textsf{OMA}$:

> For a language $L \in \mathsf{NEXP}$ decided by a machine $M$, construct a $\mathsf{NEXP}$ machine $M'$ as follows. View the $n$-bit input as a number $N$ between $1$ and $2^n$. For every $x$ of length $n$, guess a witness $w\_x$ and run $M(x,w\_x)$ to verify it. $M'(N)$ accepts if and only if $M$ accepts for at least $N$ values of $x$. The guesses are arranged such that a succinct description of a witness for $M'$ is a circuit $C$ which computes the map $(x,i) \mapsto$ the $i$-th bit of $w\_x$. Now suppose that $N$ is precisely the number of strings in $L$ at length $n$. Then succinct witnesses for $M'$ on input $N$ are circuits that simultaneously encode *all* of $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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.9919) 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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.4807) 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}$.

> **Comments:**
> **username_2**: BTW, don't trust citeseer to have the most recent (or even the best-rendered) versions of my papers. Here's better :) http://web.stanford.edu/~rrwill/projects.html  
> **username_1**: Thanks for the advice! I'll keep it in mind for the future (and that it likely applies to other authors as well).  

---

