First one must mention the beautiful paper of Impagliazzo, Kabanets and Wigderson that show that NEXP in P/poly if and only if NEXP equals MA.
NEXP not in P/poly should be much easier to prove than NP not in P/poly, as NEXP is a much larger class than NP. Also NEXP not in P/poly is just below the limit of what we can prove. We know that MAEXP, the exponential time version of MA, is not contained in P/poly. MAEXP sits just above NEXP and under some reasonable derandomization assumptions, MAEXP = NEXP.
There is also the issue of uniformity. If one can use the nondeterminism to reduce the advice just a little bit than one could then diagonalize against the P/poly machine. Also if one could slightly derandomize MA machines than one could diagonalize NEXP from MA and thus from P/poly.
Still the problem remains difficult. BPP is contained in P/poly and we don't even know whether BPP is different than NEXP. Virtually any weak unconditional derandomization of BPP would separate it from NEXP but so far we seem stuck.
We know BPP is in MA. BPP\cap NP has single quantification. Let the verifier machine for NP be M1. Let the verifier machine for MA be M1'. Let BPP machine be M. Let L1 be in BPP\cap NP. Let L2 be in BPP.
ReplyDeleteCan we say x is in L1 iff \exists r: M(x,r) accepts and M1(x) accepts?
(We know from proof of BPP in P/poly such a truthful r exists which can be checked with M1)
Likewise can we say x is in L2 iff \exists r,r': M(x,r) accepts and M1'(x,r') accepts?
This would be single quantification of BPP if correct. I know in Sipser-Gacs the random string occurs in forall quantifier. That seems to change the semantic meaning of their \Sigma_2^P sentence compared to here. But wanted to clarify anyways. What goes wrong with this naive single quantification?