Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] NEXP not in P/poly?

Expand Messages
  • Lance Fortnow
    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
    Message 1 of 1 , Feb 11, 2003
    • 0 Attachment
      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.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 2/11/2003 5:05:29 PM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.