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 restrictions on the number of queries the reductions can make.

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}_\Vert$. We also handle reductions from $NP$ to the polynomial-time hierarchy and beyond, under restrictions on the number of queries the reductions can make.

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 $\text{BPP}_\text{path}$. The latter class contains $\text{P}^\text{NP}_\Vert$ and captures the power of randomized computations conditioned on efficiently testable events. We also handle reductions from NP to the polynomial-time hierarchy and beyond, under restrictions on the number of queries the reductions can make.

We prove that relative to an oracle, there is no worst-case to errorless-average-case reduction for $\NP$. This result is the first progress on an open problem posed by Impagliazzo in 1995, namely to construct an oracle relative to which $\NP$ is worst-case hard but errorless-average-case easy. We also handle classes that are somewhat larger than $\NP$. In fact, we prove that relative to an oracle, there is no worst-case to errorless-average-case reduction from $\NP$ to $\BPPpath$. The latter class contains $\p^\NP_\Vert$ and captures the power of randomized computations conditioned on efficiently testable events. We also handle reductions from $\NP$ to the polynomial-time hierarchy and beyond, under restrictions on the number of queries the reductions can make.