Computer Science/Discrete Mathematics Seminar II

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.