Non-relativization of complexity issues can be interpreted as giving evidence that these issues cannot be resolved by Â“black-boxÂ” techniques. We show that the assumption $DistNP \subseteq AvgP$ does not imply that $NP\subseteq 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, $NP \cap co-NP$ requires exponential sized circuits. We also show that average-case easiness for $NP$ does not imply average-case easiness for the polynomial hierarchy.
University of California, San Diego; Member, School of Mathematics
March 8, 2011