3
$\begingroup$

(Also posted on mathoverflow) Given two rationals $a,b \in \mathbb{Q}$, call $c = a + ib$, i.e., the complex number represented by these two rationals.

A point $c$ is contained within the Mandelbrot Set $M$ if the following procedure never halts:

$z = c$

$while (abs(z) <= 2)$

$\hspace{0.3in} z = z*z+c$

Normally we pick some $k$ (say, 50) and then if it doesn't halt after that many iterations we assume it is in the Mandelbrot set and stop looping. Is there a polynomial time algorithm for determining if a given $c$ does not break out of this loop after $k$ steps, in terms of the magnitude of $k$ and in terms of $n$ bits representing the numerator and $n$ bits representing the denominator of $a$ and $b$?

For reference, $abs(c) = \sqrt{a^2 + b^2}$ and $c*c = a^2 + 2abi +b^2i^2 = a^2 - b^2 + 2abi$ because $i^2 = -1$.

$\endgroup$
  • 1
    $\begingroup$ Simultaneously cross-posted at mathoverflow.net/questions/283309/… $\endgroup$ – Emil Jeřábek Oct 12 '17 at 7:55
  • 1
    $\begingroup$ This question (and answers) seem to address the issue: math.stackexchange.com/questions/1035215/… $\endgroup$ – Shaull Oct 12 '17 at 9:43
  • $\begingroup$ @EmilJeřábek sorry about that, this being closed then makes sense. However, it has been about 10 months since I posted it there and it still doesn't have a good answer besides a heuristic I found. Computational complexity being a more natural fit for this community anyway, could my question be opened again now? $\endgroup$ – Phylliida Jul 27 '18 at 3:45
  • $\begingroup$ I doubt you can get any better answer than on mathoverflow (i.e., there is likely no such algorithm, but this would be difficult to prove), but whatever. I can vote to reopen the question, but you need to include a link to the MO post in the question (comments are not guaranteed to stay). $\endgroup$ – Emil Jeřábek Aug 8 '18 at 8:10
  • $\begingroup$ The paper The Complexity of the Real Line is a Fractal is only tangentially related, but might nonetheless be interesting to those interested in the topic of the post. $\endgroup$ – Neal Young Aug 11 '18 at 2:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.