Hyperbolic Julia sets are poly-time computable

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)17-30
Number of pages14
JournalElectronic Notes in Theoretical Computer Science
Volume120
Issue numberSPEC. ISS.
DOIs
StatePublished - Feb 3 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Complex dynamics
  • Computable analysis
  • Computational complexity
  • Julia sets

Fingerprint Dive into the research topics of 'Hyperbolic Julia sets are poly-time computable'. Together they form a unique fingerprint.

  • Cite this