7
$\begingroup$

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

$\endgroup$
2
  • 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 Hansen Jan 18 at 9:19
  • $\begingroup$ @KristofferArnsfeltHansen. Thanks for the clarification. $\endgroup$ – Mohsen Ghorbani Jan 18 at 9:37
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, it is a good one. $\endgroup$ – Mohsen Ghorbani Jan 18 at 8:18
  • 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$ – Ryan Williams Jan 18 at 23:20
6
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Thank you for your answer. even better $MA_{EXP} \not \subset P/poly$ $\endgroup$ – Mohsen Ghorbani Jan 18 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$ – 1.. Jan 18 at 18:26
  • $\begingroup$ I thought it is obvious, but I can't find oracles for NEXP vs MA too. $\endgroup$ – Mohsen Ghorbani Jan 18 at 22:19
  • 4
    $\begingroup$ NEXP vs MA is discussed here: math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf P.12, Theorem 23 $\endgroup$ – Avi Tal Jan 18 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.