ECCC-Report TR10-042https://eccc.weizmann.ac.il/report/2010/042Comments and Revisions published for TR10-042en-usTue, 12 Jun 2012 05:23:42 +0300
Revision 3
| Relativized Worlds Without Worst-Case to Average-Case Reductions for NP |
Thomas Watson
https://eccc.weizmann.ac.il/report/2010/042#revision3We 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.Tue, 12 Jun 2012 05:23:42 +0300https://eccc.weizmann.ac.il/report/2010/042#revision3
Revision 2
| Relativized Worlds Without Worst-Case to Average-Case Reductions for NP |
Thomas Watson
https://eccc.weizmann.ac.il/report/2010/042#revision2We 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.Mon, 13 Sep 2010 00:03:34 +0200https://eccc.weizmann.ac.il/report/2010/042#revision2
Revision 1
| Relativized Worlds Without Worst-Case to Average-Case Reductions for NP |
Thomas Watson
https://eccc.weizmann.ac.il/report/2010/042#revision1We 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.
Mon, 21 Jun 2010 16:56:08 +0300https://eccc.weizmann.ac.il/report/2010/042#revision1
Paper TR10-042
| Relativized Worlds Without Worst-Case to Average-Case Reductions for NP |
Thomas Watson
https://eccc.weizmann.ac.il/report/2010/042We 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.Fri, 12 Mar 2010 01:07:51 +0200https://eccc.weizmann.ac.il/report/2010/042