We explain our recent results [21] on the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators. This work is motivated by the desire of showing the limits of black-box reductions to some distributional NP problem. We show that a black-box nonadaptive randomized reduction to any distinguisher for (not only polynomial-time but also) exponential-time computable hitting set generators can be simulated in AM n coAM; we also show an upper bound of S_2~NP even if there is no computational bound on a hitting set generator. These results provide additional evidence that the recent worst-case to average-case reductions within NP shown by Hirahara (2018, FOCS) are inherently non-black-box. (We omit all detailed arguments and proofs, which can be found in [21].)
展开▼
机译：我们解释了关于（但不一定是可计算的）命中集合生成器的任意区分器的计算能力的最新结果[21]。这项工作的动机是希望显示出黑盒还原对某些分布NP问题的局限性。我们表明，可以在AM n coAM中模拟黑盒非自适应随机归约到任何区分器（不仅是多项式时间，而且还有指数时间的可计算命中集生成器）。即使命中集生成器上没有计算界限，我们也显示了S_2〜NP的上限。这些结果提供了更多证据，证明平原（2018，FOCS）显示的NP中最近最坏情况到平均情况的减少本质上不是黑匣子。 （我们省略了所有详细的论点和证明，可在[21]中找到。）
展开▼
