# Why should we believe that $NEXP \not \subset P/poly$

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 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$$.

• 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. Commented Jan 18, 2021 at 9:19
• @KristofferArnsfeltHansen. Thanks for the clarification. Commented Jan 18, 2021 at 9:37

The best evidence is in my opinion follows due to the results of Ryan Williams 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?.

• 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 people.csail.mit.edu/rrw/likelihoods.pdf Commented Jan 18, 2021 at 23:20

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.

• Thank you for your answer. even better $MA_{EXP} \not \subset P/poly$ Commented Jan 18, 2021 at 12:08
• @AviTal Is there an oracle which gives $EXP^O\subset BPP^O$ and $NEXP^O\not\subset BPP^O$? Commented Jan 18, 2021 at 18:26
• NEXP vs MA is discussed here: math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf P.12, Theorem 23 Commented Jan 18, 2021 at 23:00