The Complexity of Malign Measures
Peter Bro Miltersen · SIAM Journal on Computing · 1993
This paper analyzes the concept of malignness, which is the property of probability ensembles making the average case running time equal to the worst case running time for a class of algorithms. The author derives lower and upper bounds on the complexity of malign ensembles, which are tight for exponential time algorithms, and which show that no polynomial time computable malign ensemble exists for the class of polynomial time algorithms. Furthermore, it is shown that for no class of superlinear algorithms a polynomial time samplable malign ensemble exists, unless every language in P has an expected polynomial time constructor.