The Computational Complexity of Some Julia Sets
Robert Rettinger, Klaus Weihrauch · Electronic Notes in Theoretical Computer Science · 2002
Numerous computer programs have been written to compute sets of points which approximate Julia sets [4]. Usually, no error estimations are added so that it remains unclear, how good such approximations are. Furthermore, high precision pictures are unreliable because of rounding errors, since the realizing computer programs use fixed length floating point numbers. Computable error estimation w.r.t. the Hausdorff metric dH means that the set is recursive [10]. Many Julia sets J are recursive [11]. Recursive compact subsets of the Euclidean plane have a computable Turing machine time complexity [10]. In this paper we prove that the Julia set of a complex function f(z) = z2 + c for ∥c∥ < 1/4 can be computed locally in time O(k2M(k)) (where M(k) is a time bound for multiplication of k-bit integers). Roughly speaking, the local time complexity is the number of Turing machine steps to decide for a single point whether it belongs to a grid Kk ⊆ (2−k · Z )2 such that dH(Kk,J) ≤ = 2−k.