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 but in hindsight I thought it actually fit better here)

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)

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. 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^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)

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 but in hindsight I thought it actually fit better here)