3 papers
cs.LO2004
The Arithmetical Complexity of Dimension and Randomness
John M. Hitchcock, Jack H. Lutz, Sebastiaan A. Terwijn
Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a d…
cs.CC2003
Small Spans in Scaled Dimension
John M. Hitchcock
Juedes and Lutz (1995) proved a small span theorem for polynomial-time many-one reductions in exponential time. This result says that for language A decidable in exponential time,…
cs.CC2002
Effective Strong Dimension, Algorithmic Information, and Computational Complexity
Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz +1
The two most important notions of fractal dimension are {\it Hausdorff dimension}, developed by Hausdorff (1919), and {\it packing dimension}, developed by Tricot (1982). Lutz (200…