Small Spans in Scaled Dimension

DOI10.1137/S0097539703426416zbMath1101.68035MaRDI QIDQ4651530

John M. Hitchcock

Publication date: 21 February 2005

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

zbMATH Keywords

resource-bounded dimensionpolynomial-time degreessmall span theorems

Mathematics Subject Classification ID

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

Related Items

Effective fractal dimensions, Generic density and small span theorem, Partial bi-immunity, scaled dimension, and NP-completeness, Dimension, entropy rates, and compression, Scaled dimension and the Kolmogorov complexity of Turing-hard sets