Almost every real quadratic polynomial has a poly-time computable Julia set (Q1785010)

This paper addresses the problem of understanding the typical amount of computational resources (computational complexity) needed to compute quadratic Julia sets. It is shown that almost all real quadratic Julia sets are computable in polynomial time. As the authors mention, polynomial-time computability corresponds to what ``can be simulated efficiently in practice, indeed, in known applications, this is generally the case'' and hence this result can be roughly interpreted as stating that the computation of a typical quadratic Julia set is not ``hard'' from a computational complexity perspective. Roughly, computing a Julia set means being able to compute a pixel version of this set with arbitrary accuracy as done in Computable Analysis. Previous work by \textit{M. Braverman} and the second author [J. Am. Math. Soc. 19, No. 3, 551--578 (2006; Zbl 1099.37042)] has shown that, for the quadratic family \(f_c(z)=z^2+c\), there exists values of \(c\) for which the corresponding Julia set is not computable. Even for the case when the Julia set is computable, it can have arbitrarily high time complexity [\textit{I. Binder} et al., Commun. Math. Phys. 264, No. 2, 317--334 (2006; Zbl 1233.68138)]. However, in this paper, the authors show that, for the case where \(c\) is real, this behavior is exceptional since almost all quadratic Julia sets are computable in polynomial time. To prove polynomial time computability of quadratic Julia sets with real parameters, the authors rely on previous results (e.g. a result from \textit{A. Avila} and \textit{C. G. Moreira} [Ann. Math. (2) 161, No. 2, 831--881 (2005; Zbl 1078.37029)] which shows that for almost every real parameter c the map \(f_c(z) = z^2 + c\) is either Collet-Eckmann or hyperbolic) and they show that Collet-Eckmann rational maps have poly-time computable Julia sets.