Worst-Case Running Times for Average-Case Algorithms
Luís Filipe Antunes, Lance Fortnow · 2009
Under a standard hardness assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all polynomial-time samplable distributions. More precisely we show that if exponential time is not infinitely often in subexponential space, then the following are equivalent for any algorithm A: (1) For all P-samplable distributions mu, A runs in time polynomial on mu-average. (2) For all polynomial p, the running time for A is bounded by 2O(Kp(x)-K(x)+log(|x|))for all inputs x. where K(x) is the Kolmogorov complexity (size of smallest program generating x) and Kp(x) is the size of the smallest program generating x within time p(|x|). To prove this result we show that, under the hardness assumption, the polynomial-time Kolmogorov distribution, mp(x) = 2-Kp(x), is universal among the P-samplable distributions.