In search of an easy witness: Exponential time vs. probabilistic polynomial time
Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson
Abstract
Restricting the search space {0,1}^{n} to the set of truth tables of ``easy'' Boolean functions on log n variables, as well as using some known hardness-randomness tradeoffs, we establish a number of results relating the complexity of exponential-time and probabilistic polynomial-time complexity classes. In particular, we show that NEXP⊆P/poly implies NEXP=MA; this can be interpreted as saying that no derandomization of MA (and, hence, of promise-BPP) is possible unless NEXP contains a hard Boolean function. We also prove several downward closure results for ZPP, RP, BPP, and MA; e.g., we show EXP=BPP iff EE=BPE, where EE is the double-exponential time class and BPE is the exponential-time analogue of BPP.
Versions
- journal version in Journal of Computer and System Sciences, 65(4), 672-694,2002.
- extended abstract in Proceedings of the Sixteenth IEEE Conference on Computational Complexity (CCC'01), pages 1-11, 2001.