Computational complexity of Euclidean sets
Subtitle: hyperbolic Julia sets are poly-time computable.
Published: 2004
Language: eng
Number of pages: 90
Description: We apply the concepts developed to show that hyperbolic Julia sets are polynomial time computable. This result is a significant generalization of the result in [RW03], where polynomial time computability has been shown for a restricted type of hyperbolic Julia sets.We investigate different definitions of the computability and complexity of sets in   Rk , 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 [Wei00].
Notes: Adviser:  Stephen A. Cook.

Thesis (M.Sc.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 43-03, page: 0870.

MICR copy on microfiche (1 microfiche).