zbMATH — the first resource for mathematics

The computational complexity of some Julia sets. (English) Zbl 1192.68375
Proceedings of the thirty-fifth annual ACM symposium on theory of computing (STOC 2003), San Diego, CA, USA,. New York, NY: ACM Press (ISBN 1-58113-674-9). 177-185, electronic only (2003).
From the abstract: Although numerous computer programs have been written to compute sets of points which claim to approximate Julia sets, no reliable high precision pictures of non-trivial Julia sets are currently known. Usually, no error estimates are added and even those algorithms which work reliably in theory become unreliable in practice due to rounding errors and the use of fixed length floating point numbers. In this paper we prove the existence of polynomial-time algorithms to approximate the Julia sets of complex functions \(f(z)=z^2+c\) for \(|c|<1/4\). We give a strict computable error estimation with respect to the Hausdorff metric \(d_H\) which means that the set is recursive . Although these and many more Julia sets \(J\) are proven to be recursive and furthermore recursive compact subsets of the Euclidean plane are known to have a computable Turing machine time complexity, hardly anything is known about the computational complexity of non-trivial examples. The algorithms given in this paper compute the Julia sets locally in time \(O(k^2{\cdot} M(k))\) (where \(M(k)\) is a time bound for multiplication of two \(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 \(K_k\subseteq (2^{-k}{\cdot}{\mathbb Z})^2\) such that \(d_H(K_k,J)\leq 2^{-k}\).
For the entire collection see [Zbl 1074.68503].

68Q25 Analysis of algorithms and problem complexity
37F50 Small divisors, rotation domains and linearization in holomorphic dynamics
28A80 Fractals
Full Text: DOI