added a link to IK'04
Source Link
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.

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.

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.

Source Link
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.