TY - JOUR

T1 - Hyperbolic Julia sets are poly-time computable

AU - Braverman, Mark

N1 - Funding Information:
1 Research is partially supported by the Natural Sciences and Engineering Research Council of Canada. 2 Email: mbraverm@cs.toronto.edu

PY - 2005/2/3

Y1 - 2005/2/3

N2 - In 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-n (in which case we don't draw this pixel). In the case 2-n≤d(x,Jp(x))≤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|<1/4. We show that the machine drawing the Julia set can be made independent of the hyperbolic polynomial p, and provide some evidence suggesting that one cannot expect a much better computability result for Julia sets. We also introduce an alternative real set computability definition due to Ko, and show an interesting connection between this definition and the main definition.

AB - In 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-n (in which case we don't draw this pixel). In the case 2-n≤d(x,Jp(x))≤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|<1/4. We show that the machine drawing the Julia set can be made independent of the hyperbolic polynomial p, and provide some evidence suggesting that one cannot expect a much better computability result for Julia sets. We also introduce an alternative real set computability definition due to Ko, and show an interesting connection between this definition and the main definition.

KW - Complex dynamics

KW - Computable analysis

KW - Computational complexity

KW - Julia sets

UR - http://www.scopus.com/inward/record.url?scp=13544251459&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=13544251459&partnerID=8YFLogxK

U2 - 10.1016/j.entcs.2004.06.031

DO - 10.1016/j.entcs.2004.06.031

M3 - Article

AN - SCOPUS:13544251459

VL - 120

SP - 17

EP - 30

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

SN - 1571-0661

IS - SPEC. ISS.

ER -