Restricting the search space {0, 1}{sup}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 {is contained in} P/poly <=> NEXP = MA; this can be interpreted to say 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 <=> EE = BPE, where EE is the double-exponential time class and BPE is the exponential-time analogue of BPP.
展开▼
机译：将搜索空间{0,1} {sup} n限制在日志n变量上“简单”布尔函数的真实表集，以及使用一些已知的硬度随机性权衡，我们建立了一些与复杂性有关的结果指数时间和概率多项式复杂性等级。特别是;我们展示了Nexp {包含在} p / poly <=> nexp = ma中;这可以解释为说，除非NEXP包含硬布尔函数，否则可以不可能成为MA（以及，因此，承诺-BPP）的裂缝化。我们还证明了ZPP，RP，BPP和MA的几个向下闭合结果;例如，我们显示Exp = BPP <=> EE = BPE，其中EE是双指数时间类，BPE是BPP的指数 - 时间模拟。
展开▼
