### Mark Braverman

## Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are
Poly-Time Computable.

Graduate Department of Computer Science
University of Toronto, 2004
**Abstract**

We investigate different definitions of the computability and
complexity of sets in $\R^k$, and establish new connections between
these definitions. This allows us to connect the computability
of real functions and real sets in a new way. We show that
equivalence of some of the definitions corresponds to equivalence
between famous complexity classes. The model we use is mostly
consistent with K. Weihrauch's ``Computable Analysis" book.
We apply the concepts developed to show that hyperbolic
Julia sets are polynomial time computable. This result is
a significant generalization of a pervious result by R. Rettinger
and K. Weihrauch, where polynomial time computability has been shown for
a restricted type of hyperbolic Julia sets.

**Table of Contents**

*1. Introduction
*

*2. Computability of Real Sets
*

*3. Computational Complexity of Real Sets
*

*4. Complexity of Hyperbolic Julia Sets
*

*5. Directions of Future Work
*

*
*
**Number of pages:** 90