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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$.
answered Apr 2, 2011 at 12:46
-
$\begingroup$ 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) $\endgroup$– JiapengCommented Apr 3, 2011 at 2:24
-
1$\begingroup$ 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 . $\endgroup$ Commented Apr 4, 2011 at 18:07
-
$\begingroup$ 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. $\endgroup$– JiapengCommented Apr 5, 2011 at 12:39
-
$\begingroup$ 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). $\endgroup$ Commented Apr 5, 2011 at 13:47
-
$\begingroup$ 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)}).$ $\endgroup$– JiapengCommented Apr 5, 2011 at 15:04