Avoiding simplicity is complex

DOI10.1007/978-3-642-13962-8_1zbMATH Open1286.68247OpenAlexW2109863994MaRDI QIDQ3576185FDOQ3576185

Authors: Eric Allender 

Publication date: 29 July 2010

Published in: Programs, Proofs, Processes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13962-8_1

Recommendations

• Avoiding simplicity is complex
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Power from Random Strings
• scientific article; zbMATH DE number 1335898
• Resource-bounded Kolmogorov complexity revisited

zbMATH Keywords

complexity theoryhitting setsKolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (9)

• Avoiding simplicity is complex
• Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity
• Simplify or perish
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• Resource-bounded Kolmogorov complexity revisited
• Title not available (Why is that?)
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Simplicity Is the Point
• What Simplicity Is Not

This page was built for publication: Avoiding simplicity is complex

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3576185)