Relativized Separations of Worst-Case and Average-Case Complexities for NP
Russell Impagliazzo · 2011
Non-relativization of complexity issues can be interpreted as showing that these issues cannot be resolved by "black-box" techniques. We show that the assumption DistNP ⊆ AvgP does not imply that NP ⊆ BPP by relativizing techniques. More precisely, we give an oracle relative to which the assumption holds but the conclusion fails. Moreover, relative to our oracle, there are problems in NP ∩ Co-NP that require exponential circuit complexity. We also give an alternate version where DistNP ⊆ AvgP is true, but a problem in the second level of the polynomial hierarchy is hard on the uniform distribution.