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$.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Simultaneously cross-posted at mathoverflow.net/questions/283309/… $\endgroup$
    – Emil Jeřábek
    Oct 12, 2017 at 7:55
  • 1
    $\begingroup$ This question (and answers) seem to address the issue: math.stackexchange.com/questions/1035215/… $\endgroup$
    – Shaull
    Oct 12, 2017 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, 2018 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, 2018 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, 2018 at 2:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.