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^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 takes $O(n2^k)$ time (simply computing the above loop using something like Java's BigInteger class for the numerators and denominators and using fraction arithmetic). 
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 but in hindsight I thought it actually fit better here)
 A: You probably cannot practically do 100 iterations, at least not in the current universe. Let 
$$ f_c(z) = z^2 + c $$
and write $f_c^{\circ n}(z)$ for the $n$'th iterate of $f_c$. You want to start with a Gaussian rational number $\alpha\in\mathbb Q[i]$ and compute the exact value of $f_c^{\circ n}(\alpha)$. (I realize that you're only interested in taking $\alpha=c$, but the complexity doesn't really change that much.) Let's write the number $f_c^{\circ n}(\alpha)$ as
$$f_c^{\circ n}(\alpha) = \frac{A_n}{B_n}+\frac{C_n}{D_n}i,$$
where $A_n,B_n,C_n,D_n\in\mathbb Z$ and the fractions are in lowest terms. The problem is that the number of digits in these integers grows enormously rapidly. To be precise, the following limit converges:
$$ \hat h_c(\alpha) := 
\lim_{n\to\infty} \frac{\log\max\{|A_n|,|B_n|,|C_n|,|D_n|\}}{2^n}, $$
and it has the property that 
$$ \hat h_c(\alpha) > 0 \quad\text{if and only if $\alpha$ is not perperiodic.}$$
So if your want to compute $f_c^{\circ n}(\alpha)$ exactly for a non-perperiodic $\alpha$, you'll need to work with integers having roughly $2^n$ digits! If $n=100$, this would seem to be infeasible.
If you want more information about $ \hat h_c(\alpha)$, you can google dynamical canonical height.
