# Derandomize on nondeterministic assumptions

Is there anyone prove the results such like the follows?

If $NP\not\subseteq BP(2^{\Omega(n)}),$ then $BPP\subseteq P^{NP}$

In summary, my question it that, can we get some derandomized results based on some nondeterminitic assumptions.

-

As for derandomization under nondeterministic assumptions, you can basically relativize the usual results such as Impagliazzo-Wigderson. Directly, this gives: if some language in $E^{NP}$ requires exponential circuits with an NP-oracle, then $BPP^{NP}=P^{NP}$. There are similar results by Miltersen and Vinodchandran: if some language in $NE\cap coNE$ requires exponential-size nondeterministic circuits, then $AM = NP$.

-
Many Thanks. :) But, I call assumptions under nondeterministic, means that I don't hope there are some assumptions with circuits lower bound (which is non-uniform assumptions) –  Jiapeng Apr 3 '11 at 2:24
I'm not sure I understand what you are saying, however, I can't recall any nontrivial derandomization results where both the assumption and the conclusion are uniform. Usually the assumption is a circuit lower bound, less usually the assumption is uniform at the expense of the conclusion applying to an “infinitely often” or “heuristic” version of some complexity class. For example, if $EXP\ne MA$ then $BPP\subseteq\text{i.o.-}SUBEXP$ by Babai, Fortnow, Nisan and Wigderson. See also mathoverflow.net/questions/57350 . –  Emil Jeřábek Apr 4 '11 at 18:07
Many thanks, I have asked a similar question before. In summary, I mean that I have the following conjecture, If $E:=PTIME(2^{O(n)})\not\subseteq IP(2^{\Omega(n)}),$ then $BPP=P$, where $IP(T(n))$ is the with interactive proofs with T(n) rounds, and with running time T(n) in each round, i.e. $IP=\bigcup_{c>0}IP(n^{c}).$ I haven't proved it rigorously, but I think that it's right. –  Jiapeng Apr 5 '11 at 12:39
Sorry for the pointless link, I didn’t notice that the other question was also yours. I agree that the conjecture is likely true, since its conclusion is expected to be true, but I wouldn’t be so sure about the assumption (in view of results like MIP = NEXP, I can imagine that E does actually have subexponential interactive protocols). –  Emil Jeřábek Apr 5 '11 at 13:47
Thanks again. Your viewpoint is very reasonable, and it's very helpful for me. I think that the relationships between MIP, IP, NEXP, EXP, and E are very complex, and I will spend more time to consider the class $IP(2^{\Omega(n)}).$ –  Jiapeng Apr 5 '11 at 15:04