Polynomial-time computability of Julia sets without critical points in the postcritical set

Let ff be a rational map. Write JfJ_f for its Julia set and Ωf\Omega_f for its postcritical set. A Turing machine has an oracle for the coefficients of ff if it can access those coefficients through oracle queries.

Computability conjecture. If Ωf\Omega_f does not contain any critical points, then JfJ_f is polynomial-time computable by a Turing machine with an oracle for the coefficients of ff.

The algorithm proving the paper's main theorem does not apply when Ωf\Omega_f contains a parabolic periodic point, but the authors expect this broader computability statement to hold.

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.