Relativized Worlds without Worst-Case to Average-Case Reductions for NP
Thomas W. Watson · ACM Transactions on Computation Theory · 2012
We prove that, relative to an oracle, there is no worst-case to average-case reduction for NP. We also handle classes that are somewhat larger than NP, as well as worst-case to errorless -average-case reductions. In fact, we prove that relative to an oracle, there is no worst-case to errorless-average-case reduction from NP to BPP ∥ NP . We also handle reductions from NP to the polynomial-time hierarchy and beyond, under strong restrictions on the number of queries the reductions can make.