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
