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

Let ff be a rational map of degree d2d\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 cJfc\notin J_f either is finite or converges to an attracting periodic orbit;
  2. for any critical point cJfc\in J_f, either there exist γ,C>0\gamma,C>0 such that
Dfn(f(c))Ceγnfor any nN,|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.

Sources & referencesView supporting material

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.