Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR10-042 | 12th June 2012 05:23

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

Revision #3
Authors: Thomas Watson
Accepted on: 12th June 2012 05:23
Keywords:

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

Revision #2
Authors: Thomas Watson
Accepted on: 13th September 2010 00:03
Keywords:

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

Revision #1
Authors: Thomas Watson
Accepted on: 21st June 2010 16:56
Keywords:

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

TR10-042
Authors: Thomas Watson
Publication: 12th March 2010 01:07
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.