Showing cs.CCShow all
3 papers · 1 filter
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…
cs.CC2002
The Dimensions of Individual Strings and Sequences
Jack H. Lutz
A constructive version of Hausdorff dimension is developed using constructive supergales, which are betting strategies that generalize the constructive supermartingales used in the…
cs.CC2002
Dimension in Complexity Classes
Jack H. Lutz
A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martingales. When the resource bound Δ(a parameter of the theory) is unrestric…