Curiouser and Curiouser: The Link between Incompressibility and Complexity

DOI10.1007/978-3-642-30870-3_2zbMath1357.68089OpenAlexW1831013898MaRDI QIDQ2904388

Eric W. Allender

Publication date: 14 August 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-30870-3_2

Mathematics Subject Classification ID

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

Related Items

The Complexity of Complexity, Unnamed Item, Sets with small generalized Kolmogorov complexity