MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
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 . – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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