The Complexity of Malign Measures

DOI10.1137/0222012zbMath0767.68065OpenAlexW2042051386MaRDI QIDQ4037690

Peter Bro Miltersen

Publication date: 16 May 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222012

zbMATH Keywords

average case complexitymalignness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

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 ⋮ An average complexity measure that yields tight hierarchies ⋮ Transformations that preserve malignness of universal distributions ⋮ Transformations that preserve malignness of universal distributions ⋮ Polynomial time samplable distributions

This page was built for publication: The Complexity of Malign Measures