Hyperbolic Julia Sets are Poly-Time Computable

AbstractIn this paper we prove that hyperbolic Julia sets are locally computable in polynomial time. Namely, for each complex hyperbolic polynomial p(z), there is a Turing machine Mp(z) that can “draw” the set with the precision 2−n, such that it takes time polynomial in n to decide whether to draw each pixel. In formal terms, it takes time polynomial in n to decide for a point x whether d(x,Jp(z))<2−n (in which case we draw a pixel with center x), or d(x,Jp(z))>2⋅2−n (in which case we don't draw this pixel). In the case 2−n≤d(x,Jp(x))≤2⋅2−n either answer will be acceptable. This definition of complexity for sets is equivalent to the definition introduced in Weihrauch's book [Weihrauch, K., “Computable Analysis”, Springer, Berlin, 2000] and used by Rettinger and Weihrauch in [Rettinger, R, K Weihrauch, The Computational Complexity of Some Julia Sets, in STOC'03, June 9-11, 2003, San Diego, California, USA].Although the hyperbolic Julia sets were shown to be recursive, complexity bounds were proven only for a restricted case in [Rettinger, R, K Weihrauch, The Computational Complexity of Some Julia Sets, in STOC'03, June 9-11, 2003, San Diego, California, USA]. Our paper is a significant generalization of [Rettinger, R, K Weihrauch, The Computational Complexity of Some Julia Sets, in STOC'03, June 9-11, 2003, San Diego, California, USA], in which polynomial time computability was shown for a special kind of hyperbolic polynomials, namely, polynomials of the form p(z)=z2+c with |c|