One of the central open questions in the theory of average-case complexity is to establish the equivalence between the worst-case and average-case complexity of the Polynomial-time Hierarchy (PH). One general approach is to show that there exists a PH-computable hitting set generator whose security is based on some NP-hard problem. We present the limits of such an approach, by showing that there exists no exponential-time-computable hitting set generator whose security can be proved by using a nonadaptive randomized polynomial-time reduction from any problem outside AM intersect coAM, which significantly improves the previous upper bound $BPP^NP$ of Gutfreund and Vadhan (RANDOM/APPROX 2008). In particular, any security proof of a hitting set generator based on some NP-hard problem must use either an adaptive or non-black-box reduction (unless the polynomial-time hierarchy collapses).

Based on our results, we argue that the recent worst-case to average-case reduction of Hirahara (FOCS 2018) is inherently non-black-box, without relying on any unproven assumptions. On the other hand, combining the non-black-box reduction with our simulation technique of black-box reductions, we exhibit the existence of a ``non-black-box selector'' for GapMCSP, i.e., an efficient algorithm that solves GapMCSP given as advice two circuits one of which is guaranteed to compute GapMCSP.

The current version is a full version of the RANDOM'20 paper. Some results that appeared in the first author's ITCS'20 paper are removed.

We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of 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 even) exponential-time computable hitting set generators can be simulated in AM $\cap$ coAM; we also show an upper bound of $\mathrm{S_2^{NP}}$ even if there is no computational bound on a hitting set generator. These results further strengthen the evidence that the recent worst-case to average-case reductions within NP shown by Hirahara (2018, FOCS) are inherently non-black-box. As an application, we show that GapMCSP $\in$ P/poly implies that GapMCSP is low for $\mathrm{S_2^p}$, which is proved by combining our proof techniques with the non-black-box reductions.

Another line of research concerns the computational power of nonadaptive deterministic polynomial-time reductions to the set of Kolmogorov-random strings. It was conjectured by Allender (CiE, 2012) and others that the computational power is exactly characterized by BPP, intuitively because nonadaptive deterministic reductions could only make use of Kolmogorov-random strings as a source of pseudorandomness.

We present strong evidence *against* this conjecture by showing that every language in the exponential-time hierarchy is reducible to the set of Kolmogorov-random strings under PH reductions; in particular, the conjecture is false unless the exponential-time hierarchy collapses to BPEXP. Moreover, our reduction cannot be regarded as a black-box reduction to avoiding hitting set generators (unless the exponential-time hierarchy collapses to the second level), thereby showing that nonadaptive deterministic efficient reductions can exploit the power of Kolmogorov-random strings not just as a distinguisher for hitting set generators.