<p>Proving this separation seems very hard since we don't even know how to separate EXP^NP (which contains NEXP) from P/Poly, and we know that this separation does not algebrize. In addition, if EXP^NP ⊆ P / poly, then EXP^NP would be equal to EXP...
We also know that if NEXP ⊆ P/poly, then NEXP = MA.</p>
<p>Nevertheless, we do know that EXP^NP^NP is not in P/Poly.</p>

CC BY-SA 4.0
2021-01-18T12:08:02.833Z
Thank you for your answer. even better $MA_{EXP} \not \subset P/poly$
Mohsen Ghorbani
CC BY-SA 4.0
2021-01-18T18:26:18.407Z
@AviTal Is there an oracle which gives $EXP^O\subset BPP^O$ and $NEXP^O\not\subset BPP^O$?
Turbo
CC BY-SA 4.0
2021-01-18T23:00:01.483Z
NEXP vs MA is discussed here: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf       P.12, Theorem 23
Avi Tal
CC BY-SA 4.0
2021-01-18T11:52:19.827Z
2021-01-18T12:12:32.350Z
2021-01-18T12:12:32.350Z
Avi Tal
<p>The best evidence is in my opinion <a href="https://rjlipton.wordpress.com/2018/01/23/progress-on-the-frontier/" rel="nofollow noreferrer">follows due to the results of Ryan Williams</a> on even a mild speed up of <span class="math-container">$CIRCUITSAT$</span> provides <span class="math-container">$NQP\not\subset P/poly$</span> which is an extremely strong result compared to <span class="math-container">$NEXP\not\subset P/poly$</span>. It indicates to me that either we are missing something trivial which would separate <span class="math-container">$NEXP$</span> from <span class="math-container">$P/poly$</span> or (remotely plausibly) anything that separates <span class="math-container">$NEXP$</span> from <span class="math-container">$P/poly$</span> would separate any class slightly bigger than <span class="math-container">$NP$</span> from <span class="math-container">$P/poly$</span>.</p>
<p><strong>Update</strong> It seems all the more likely if we do not reach <span class="math-container">$NEXP\not\subset P/poly$</span> by speeding up GapCircuitSAT or CircuitSAT problems we might achieve a separation via embedding <span class="math-container">$NP$</span> problems in <span class="math-container">$MCSP$</span> in <span class="math-container">$PTIME$</span> or <span class="math-container">$LOGSPACE$</span>. It is unclear if speeding up <span class="math-container">$SAT$</span> has anything to do with embedding or vice versa. Please refer <a href="https://cstheory.stackexchange.com/questions/48369/comparing-sat-to-mcsp-reduction-class-separations-and-faster-sat-class-separatio">Comparing SAT to MCSP reduction class separations and faster SAT class separations?</a>.</p>

CC BY-SA 4.0
2021-01-18T23:20:43.833Z
In fact, a result that would be much much weaker than P=RP (that the promise problem GAP-CircuitSAT has some nontrivial algorithm) already implies NEXP not in P/poly. So if NEXP is in P/poly, then basically no nontrivial derandomization of general circuits is possible at all, yet essentially every problem we care about has a small circuit family. I don't think nonuniform computation (and randomness) can be so powerful. For more on my opinion see https://people.csail.mit.edu/rrw/likelihoods.pdf
Ryan Williams
CC BY-SA 4.0
2021-01-18T08:06:20.323Z
2021-02-11T12:03:45.807Z
2021-02-11T12:03:45.807Z
Turbo
<p>I am sorry if this is not an advanced question. Most computer scientists believed that <span class="math-container">$NEXP \not \subset P/poly$</span> but they are not even close to this assumption. The main evidence that they are used is derandomization and they believe that <span class="math-container">$P=BPP$</span> and I know Nissan and Wigderson's generator which exist if <span class="math-container">$EXP \not \subset P/poly$</span>(<span class="math-container">$E \not \subset Size(2^{o(n))}$</span>). On the other hand, I see some theorems like IP = PSPACE which thought to be false. Recently I read the <a href="https://ieeexplore.ieee.org/document/933865" rel="nofollow noreferrer">IKW</a> and there is a theorem states that <span class="math-container">$NEXP \in P/poly$</span> then there is a polynomial witness description for any language in <span class="math-container">$NEXP$</span>. For me, it is likely to happen for example Succinct-HC is an <span class="math-container">$NEXP$</span>-Complete language and it is likely to have a succinct witness. On the other hand, there are undecidable problems in P/poly that we don't know, maybe we could use them as an oracle to solve Succicnt-HC, They are some reasons in IKW‌'s paper but I need more references that help me to understand why should we believe that <span class="math-container">$NEXP \not \subset P/poly$</span>.</p>

CC BY-SA 4.0
2021-01-18T09:19:43.877Z
You got it backwards: We believe that BPP=P *because* we expect the relevant circuit lower bounds to hold! The great insight of IKW, similar and later work is that in a sense derandomization also implies circuit lower bounds.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-01-18T09:37:47.193Z
@KristofferArnsfeltHansen. Thanks for the clarification.
Mohsen Ghorbani
<circuit-complexity><derandomization><nexp>
Why should we believe that $NEXP \not \subset P/poly$
Mohsen Ghorbani
# Why should we believe that $NEXP \not \subset P/poly$

(Asked by: username_0 on 2021-01-18)

I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used is derandomization and they believe that $P=BPP$ and I know Nissan and Wigderson's generator which exist if $EXP \not \subset P/poly$($E \not \subset Size(2^{o(n))}$). On the other hand, I see some theorems like IP = PSPACE which thought to be false. Recently I read the [IKW](https://ieeexplore.ieee.org/document/933865) and there is a theorem states that $NEXP \in P/poly$ then there is a polynomial witness description for any language in $NEXP$. For me, it is likely to happen for example Succinct-HC is an $NEXP$-Complete language and it is likely to have a succinct witness. On the other hand, there are undecidable problems in P/poly that we don't know, maybe we could use them as an oracle to solve Succicnt-HC, They are some reasons in IKW‌'s paper but I need more references that help me to understand why should we believe that $NEXP \not \subset P/poly$.

**Tags:** circuit-complexity, derandomization, nexp
> **Comments:**
> **username_1**: You got it backwards: We believe that BPP=P *because* we expect the relevant circuit lower bounds to hold! The great insight of IKW, similar and later work is that in a sense derandomization also implies circuit lower bounds.  
> **username_0**: @KristofferArnsfeltHansen. Thanks for the clarification.  

---

## 2 answers

### Answer by username_3 on 2021-01-18. Score: 6 | Accepted answer

The best evidence is in my opinion [follows due to the results of Ryan Williams](https://rjlipton.wordpress.com/2018/01/23/progress-on-the-frontier/) on even a mild speed up of $CIRCUITSAT$ provides $NQP\not\subset P/poly$ which is an extremely strong result compared to $NEXP\not\subset P/poly$. It indicates to me that either we are missing something trivial which would separate $NEXP$ from $P/poly$ or (remotely plausibly) anything that separates $NEXP$ from $P/poly$ would separate any class slightly bigger than $NP$ from $P/poly$.

**Update** It seems all the more likely if we do not reach $NEXP\not\subset P/poly$ by speeding up GapCircuitSAT or CircuitSAT problems we might achieve a separation via embedding $NP$ problems in $MCSP$ in $PTIME$ or $LOGSPACE$. It is unclear if speeding up $SAT$ has anything to do with embedding or vice versa. Please refer [Comparing SAT to MCSP reduction class separations and faster SAT class separations?](https://cstheory.stackexchange.com/questions/48369/comparing-sat-to-mcsp-reduction-class-separations-and-faster-sat-class-separatio).

> **Comments:**
> **username_4**: In fact, a result that would be much much weaker than P=RP (that the promise problem GAP-CircuitSAT has some nontrivial algorithm) already implies NEXP not in P/poly. So if NEXP is in P/poly, then basically no nontrivial derandomization of general circuits is possible at all, yet essentially every problem we care about has a small circuit family. I don't think nonuniform computation (and randomness) can be so powerful. For more on my opinion see https://people.csail.mit.edu/rrw/likelihoods.pdf  

---

### Answer by username_2 on 2021-01-18. Score: 7

Proving this separation seems very hard since we don't even know how to separate EXP^NP (which contains NEXP) from P/Poly, and we know that this separation does not algebrize. In addition, if EXP^NP ⊆ P / poly, then EXP^NP would be equal to EXP...
We also know that if NEXP ⊆ P/poly, then NEXP = MA.

Nevertheless, we do know that EXP^NP^NP is not in P/Poly.

> **Comments:**
> **username_0**: Thank you for your answer. even better $MA_{EXP} \not \subset P/poly$  
> **username_3**: @AviTal Is there an oracle which gives $EXP^O\subset BPP^O$ and $NEXP^O\not\subset BPP^O$?  
> **username_2**: NEXP vs MA is discussed here: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf       P.12, Theorem 23  

---

