<p>(Also posted on <a href="https://mathoverflow.net/questions/283309/complexity-of-the-mandelbrot-set-on-rationals">mathoverflow</a>) Given two rationals $a,b \in \mathbb{Q}$, call $c = a + ib$, i.e., the complex number represented by these two rationals.</p>

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

<p>$z = c$</p>

<p>$while (abs(z) &lt;= 2)$</p>

<p>$\hspace{0.3in} z = z*z+c$</p>

<p>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$?</p>

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

CC BY-SA 3.0
2017-10-12T07:55:32.103Z
Simultaneously cross-posted at https://mathoverflow.net/questions/283309/complexity-of-the-mandelbrot-set-on-rationals
Emil Jeřábek
CC BY-SA 3.0
2017-10-12T09:43:26.407Z
This question (and answers) seem to address the issue: https://math.stackexchange.com/questions/1035215/is-it-possible-to-prove-that-some-point-belongs-to-mandelbrot-set-is-this-an-ex
Shaull
CC BY-SA 4.0
2018-07-27T03:45:23.400Z
@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?
Phylliida
CC BY-SA 4.0
2018-08-08T08:10:16.913Z
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).
Emil Jeřábek
CC BY-SA 4.0
2018-08-11T02:08:52.577Z
The paper *[The Complexity of the Real Line is a Fractal](https://scholar.google.com/scholar?hl=en&as_sdt=1%2C22&q=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.
Neal Young
<cc.complexity-theory><ds.algorithms><time-complexity><space-complexity><fractals>
Complexity of the mandelbrot set on rationals
Phylliida
# Complexity of the mandelbrot set on rationals

(Asked by: username_0 on 2017-10-11)

(Also posted on [mathoverflow](https://mathoverflow.net/questions/283309/complexity-of-the-mandelbrot-set-on-rationals)) 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$.

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, space-complexity, fractals
> **Comments:**
> **username_1**: Simultaneously cross-posted at https://mathoverflow.net/questions/283309/complexity-of-the-mandelbrot-set-on-rationals  
> **username_2**: This question (and answers) seem to address the issue: https://math.stackexchange.com/questions/1035215/is-it-possible-to-prove-that-some-point-belongs-to-mandelbrot-set-is-this-an-ex  
> **username_0**: @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?  
> **username_1**: 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).  
> **username_3**: The paper *[The Complexity of the Real Line is a Fractal](https://scholar.google.com/scholar?hl=en&as_sdt=1%2C22&q=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.  

---

## 0 answers

