On computational complexity of Siegel Julia sets

DOI10.1007/S00220-006-1546-3zbMATH Open1233.68138arXivmath/0502354OpenAlexW3098936822WikidataQ122442267 ScholiaQ122442267MaRDI QIDQ984472FDOQ984472

Mark Braverman, Ilia Binder, Michael Yampolsky

Publication date: 19 July 2010

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Abstract: It has been previously shown by two of the authors that some polynomial Julia sets are algorithmically impossible to draw with arbitrary magnification. On the other hand, for a large class of examples the problem of drawing a picture has polynomial complexity. In this paper we demonstrate the existence of computable quadratic Julia sets whose computational complexity is arbitrarily high.

Full work available at URL: https://arxiv.org/abs/math/0502354

Recommendations

• Computability of Julia sets
• Non-computable Julia sets
• The computational complexity of some Julia sets
• Real quadratic Julia sets can have arbitrarily high complexity
• Almost every real quadratic polynomial has a poly-time computable Julia set

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Dynamics of complex polynomials, rational maps, entire and meromorphic functions; Fatou and Julia sets (37F10) Small divisors, rotation domains and linearization in holomorphic dynamics (37F50) Constructive and recursive analysis (03F60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Brjuno functions and their regularity properties
• Title not available (Why is that?)
• Iteration of analytic functions
• The computational complexity of some julia sets
• Title not available (Why is that?)
• Self-similarity of Siegel disks and Hausdorff dimension of Julia sets
• Title not available (Why is that?)
• The Brjuno function continuously estimates the size of quadratic Siegel disks
• Mating Siegel quadratic polynomials
• Non-computable Julia sets
• Filled Julia sets with empty interior are computable
• Parabolic Julia sets are polynomial time computable
• Variation of the conformal radius

Cited In (14)

• Statistical properties of dynamical systems -- Simulation and abstract computation
• Computability of Julia sets
• Probability, statistics and computation in dynamical systems
• Almost every real quadratic polynomial has a poly-time computable Julia set
• Computable Geometric Complex Analysis and Complex Dynamics
• Non-computable Julia sets
• Computability of the Julia set. Nonrecurrent critical orbits
• Positive reducibility of the interior of filled Julia sets
• Constructing locally connected non-computable Julia sets
• Title not available (Why is that?)
• Real quadratic Julia sets can have arbitrarily high complexity
• Poly-time computability of the Feigenbaum Julia set
• Computability of Brolin-Lyubich measure
• Computability of Julia sets

This page was built for publication: On computational complexity of Siegel Julia sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q984472)