Kaveh
• 21.2k
• 8
• 79
• 179

For one, proving $$BPP \subseteq NP$$ would easily imply that $$NEXP \neq BPP$$, which already means that your proof can't relativize.

But let's look at something even weaker: $$coRP \subseteq NTIME[2^{n^{o(1)}}]$$. If that is true, then polynomial identity testing for arithmetic circuits is in nondeterministic subexponential time. By Impagliazzo-Kabanets'04Impagliazzo-Kabanets'04, such an algorithm implies circuit lower bounds: either the Permanent does not have poly-size arithmetic circuits, or $$NEXP \not\subset P/poly$$.

I personally don't know why it looks "out of reach" but it does seem hard to prove. Certainly some genuinely new tricks will be needed to prove it.

Ryan Williams
• 26.1k
• 6
• 110
• 158

For one, proving $$BPP \subseteq NP$$ would easily imply that $$NEXP \neq BPP$$, which already means that your proof can't relativize.

But let's look at something even weaker: $$coRP \subseteq NTIME[2^{n^{o(1)}}]$$. If that is true, then polynomial identity testing for arithmetic circuits is in nondeterministic subexponential time. By Impagliazzo-Kabanets'04, such an algorithm implies circuit lower bounds: either the Permanent does not have poly-size arithmetic circuits, or $$NEXP \not\subset P/poly$$.

I personally don't know why it looks "out of reach" but it does seem hard to prove. Certainly some genuinely new tricks will be needed to prove it.