Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #3
Authors: Thomas Watson
Accepted on: 12th June 2012 05:23
Downloads: 2508
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
Downloads: 2762
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
Downloads: 2724
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
Downloads: 2959
Keywords: 


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.



ISSN 1433-8092 | Imprint