Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-018 | 27th March 1995 00:00

Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions

RSS-Feed




TR95-018
Authors: Jay Belanger, Jie Wang
Publication: 7th April 1995 00:55
Downloads: 1839
Keywords: 


Abstract:

We show that polynomially rankable distributions
do not provide harder instances than uniform distributions
for NP problems. In particular, we show that if Levin's
randomized tiling problem is solvable in polynomial time on
average, then every NP problem under any p-rankable
distribution is solvable in average polynomial time
with respect to rankability. We then present a reasonably
tight hierarchy result for average-case
complexity classes under uniform distributions.

Keyword: Average-Case NP-Completeness, Rankable Distributions,
Uniform Distributions, Randomizing Reductions.



ISSN 1433-8092 | Imprint