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$.
-
5$\begingroup$ 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. $\endgroup$– Kristoffer Arnsfelt HansenCommented Jan 18, 2021 at 9:19
-
$\begingroup$ @KristofferArnsfeltHansen. Thanks for the clarification. $\endgroup$– Mohsen GhorbaniCommented Jan 18, 2021 at 9:37
2 Answers
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?.
-
5$\begingroup$ 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 $\endgroup$ 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.
-
1$\begingroup$ Thank you for your answer. even better $MA_{EXP} \not \subset P/poly$ $\endgroup$ Commented Jan 18, 2021 at 12:08
-
2$\begingroup$ @AviTal Is there an oracle which gives $EXP^O\subset BPP^O$ and $NEXP^O\not\subset BPP^O$? $\endgroup$– TurboCommented Jan 18, 2021 at 18:26
-
4$\begingroup$ NEXP vs MA is discussed here: math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf P.12, Theorem 23 $\endgroup$– Avi TalCommented Jan 18, 2021 at 23:00