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 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 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 P/poly implies that GapMCSP is low for 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.
展开▼
