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^2+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. The ordinary algorithm for this requires $O(n2^k)$ calculations. Is there a polynomial time algorithm for determining if a given $c$ breaks out of this loop within $k$ steps, in terms of the magnitude of $k$ and in terms of $n$ bits representing the numerator and denominator of $a$ and $b$? For reference, $abs(c) = \sqrt{a^2 + b^2}$ and $c^2 = a^2 + 2abi +b^2i^2 = a^2 - b^2 + 2abi$ because $i^2 = -1$. (this was [cross posted at cstheory stackexchange](https://cstheory.stackexchange.com/questions/39275/complexity-of-the-mandelbrot-set-on-rationals) but in hindsight I thought it actually fit better here)