Polynomial-time computability of Julia sets under the critical-orbit dichotomy
Polynomial-time computability of Julia sets under the critical-orbit dichotomy
Let be a rational map of degree , let denote its Julia set, and let denote the derivative of the -th iterate. Assume the following two conditions:
- the forward orbit of every critical point either is finite or converges to an attracting periodic orbit;
- for any critical point , either there exist such that
or the forward orbit of contains another critical point.
Computability conjecture. Under these two conditions, is polynomial-time computable by a Turing machine with an oracle for the coefficients of .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.