Worst-Case Running Times for Average-Case Algorithms

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2009

Autores

antunes, l (Autor) FCUP; fortnow, l (Autor) Outra

Ata de Conferência Internacional

Título: PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY

Páginas: 298-+

24th Annual IEEE Conference on Computational Complexity

Paris, FRANCE, JUL 15-18, 2009

Indexação

ISI Web of Knowledge - 13 Citações

Scopus - 24 Citações

Outras Informações

ID Authenticus: P-003-RRV

DOI: 10.1109/ccc.2009.12

Abstract (EN): 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: For all P-samplable distributions mu, A runs in time polynomial on mu-average. For all polynomial p, the running time for A is bounded by 2(O(Kp(x)-K(x)+log(|x|))) for all inputs x. where K(x) is the Kolmogorov complexity (size of smallest program generating x) and K-p(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, m(p)(x) = 2(-Kp(x)), is universal among the P-samplable distributions.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 3