Generic density and small span theorem

DOI10.1016/J.IC.2007.10.001zbMath1133.68021OpenAlexW1973754982MaRDI QIDQ2475804

Philippe Moser

Publication date: 11 March 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://eprints.maynoothuniversity.ie/8243/1/PM-Generic-2008.pdf

zbMATH Keywords

genericityresource-bounded dimensionsmall span theorem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Almost everywhere high nonuniform complexity
• Genericity and randomness over feasible probability measures
• Genericity and measure for exponential time
• Prediction and dimension
• Finite-state dimension
• The dimensions of individual strings and sequences
• Hard sets are hard to find
• Baire categories on small complexity classes and meager-comeager laws
• Effective fractal dimensions
• Category and Measure in Complexity Classes
• Small Spans in Scaled Dimension
• STACS 2004
• Fundamentals of Computation Theory

This page was built for publication: Generic density and small span theorem