Fractals in complexity and geometry.

摘要

Fractal dimensions have been used by mathematicians and physicists to study properties of dynamic systems and geometry for around a century and have been used by computer scientists to study complexity classes for two decades. But in computer science, the usefulness of fractal dimensions was very limited before Lutz effectivized classical Hausdorff dimension to effective dimensions in 2000. With effective dimensions, a singleton set may have the full dimension of the entire space. This enables us to use dimension-theoretic tools to study the structure of complexity classes which are typically countable sets and to study fractal properties of individual points in Euclidean spaces.;Using these new dimension-theoretic tools, we study both dimensionality and fractal geometry in a computationally resource bounded setting. On the dimensionality front, we will discuss the power of nontrivial fractals in terms of derandomization, the fractal dimension of certain complexity classes, and some relationship between fractal dimension and normality. For fractal geometry, we will discuss some new results in computable analysis, which will include an effective extension of the famous analyst's Traveling Salesman Theorem from geometric measure theory and the existence of a wicked simple curve that forces a computer to retrace. These results are not dimension-theoretic in nature. But the geometric constructions involved do share some features of common fractals.