Average case complexity under the universal distribution equals worst- case complexity

DOI10.1016/0020-0190(92)90138-LzbMath0780.68064MaRDI QIDQ1198047

Paul M. B. Vitányi, Ming Li

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

sortingKolmogorov complexityanalysis of algorithmsuniform distributiontime complexityaverage complexityworst-case complexityquicksortspace complexityuniversal distributionaverage NP completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Computational depth: Concept and applications ⋮ Generalized juntas and NP-hard sets ⋮ Average-case analysis via incompressibility ⋮ Some properties of sets tractable under every polynomial-time computable distribution ⋮ Transformations that preserve malignness of universal distributions ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Transformations that preserve malignness of universal distributions ⋮ The miraculous universal distribution ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Unnamed Item ⋮ Malign distributions for average case circuit complexity.

Cites Work

• Unnamed Item
• Unnamed Item
• Average Case Complete Problems
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A formal theory of inductive inference. Part II