Tuesday, February 11, 2003

NEXP not in P/poly?

Daniel Varga asks about the question of NEXP not in P/poly and whether it is "fundamentally" easier than NP not in P/poly. As a reminder: NEXP is the class of languages accepted in nondeterministic exponential (2nO(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 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.

No comments:

Post a Comment