On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.

摘要: 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 desire showing limits black-box reductions to some distributional \(\mathsf {NP}\) problem. show that a nonadaptive randomized reduction any only polynomial-time but also) exponential-time computable generators can be simulated in {AM}\cap \mathsf {co} {AM}\); we also upper bound {S}_2^\mathsf even if there no generator. These provide additional evidence worst-case average-case within shown Hirahara (2018, FOCS) are inherently non-black-box. (We omit all detailed arguments and proofs, which found [21].)