### Revision(s):

__
Revision #3 to TR10-042 | 12th June 2012 05:23
__
#### Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

**Abstract:**
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.

__
Revision #2 to TR10-042 | 13th September 2010 00:03
__
#### Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

**Abstract:**
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.

__
Revision #1 to TR10-042 | 21st June 2010 16:56
__
#### Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

**Abstract:**
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.

### Paper:

__
TR10-042 | 12th March 2010 00:18
__

#### Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

**Abstract:**
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.