Polynomial-time computability of Julia sets under the critical-orbit dichotomy

About 15 years old · traced to

Let ff be a rational map of degree d⩾2d\geqslant 2, let JfJ_f denote its Julia set, and let DfnDf^n denote the derivative of the nn-th iterate. Assume the following two conditions:

  1. the forward orbit of every critical point c∉Jfc\notin J_f either is finite or converges to an attracting periodic orbit;
  2. for any critical point c∈Jfc\in J_f, either there exist γ,C>0\gamma,C>0 such that
∣Dfn(f(c))∣⩾Ceγnfor any n∈N,|Df^n(f(c))|\geqslant Ce^{\gamma n}\quad\text{for any }n\in\mathbb{N},

or the forward orbit of cc contains another critical point.

Computability conjecture. Under these two conditions, JfJ_f is polynomial-time computable by a Turing machine with an oracle for the coefficients of ff.

This is presented as a generalization of the paper's main computability theorem. Together with the preceding typical critical-orbit conjecture, it motivates the expectation that Julia sets are polynomial-time computable for almost all rational maps, but the source gives no proof of this generalization.

References

Primary source

Artem Dudko, “Computability of the Julia set. Nonrecurrent critical orbits”, arXiv:1109.2946 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.