^{nO(1)}) time. P/poly are languages accepted by nonuniform polynomial-size circuits, or equivalently by a polynomial time machine given a polynomial amount of "advice" that depends only on the input size.

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
MA_{EXP}, the exponential time version of MA, is not contained in
P/poly. MA_{EXP} sits just above NEXP and under some reasonable
derandomization assumptions, MA_{EXP} = 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.

## No comments:

## Post a Comment