Showing cs.CCShow all
2 papers · 1 filter
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…