Complexity of a variant of the Mandelbrot set decision problem? Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$  where $c$ is a complex number

Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded and some number $P^n_c (0)$ has a complex magnitude greater than 2 (but less than $m$) for some integer $n$ > $k$}

Assume $k$ and $m$ are integers given in unary encoding


  Is there an efficient algorithm in the real computing model (i.e the Blum-Shub-Smale model) for deciding set $M$ ?


Essentially, I'm asking if there exists efficient algorithm that decides whether the sequence is UNBOUNDED such that breakaway occurs at a number of iterations more than K.

UPDATE: The problem is in $NP$ since there is a polynomially verifiable certificate of membership.


  So, Is there an efficient algorithm or is it $NP$-hard to decide set $M$?


The problem went through major changes for these reasons:

1-For the problem to be interesting, "&lt;" was changed to ">" in the definition.

2-I wanted the problem to be in $NP$, so I introduced parameter $m$.

Also, the bounty may be awarded to the first person who poses an $NP$-complete problem related to Mandelbrot Set
Let's look at $M$ for fixed $k$ first.

Given a fixed $k$ in unary, the problem essentially reduces to figuring out the algebraic set $|P_c^{(k)}(0)| = 2$.  Since the level sets 'at infinity' are properly nested, the question becomes a membership test in an algebraic set.  The issue is that the minimal polynomial is of degree $2^k$.  However, one can represent it as a straight-line problem of size $k$.

So then the question becomes: what is your arithmetic model?  You'll need arbitrary precision arithmetic to do this 'right', and then counting bit operations or counting "real number" operations will give radically different answers [NP-hardness is rather fragile that way, unlike 'computability'].

For arbitrary $k$, things get messier still.  It really depends on whether one would have a uniform modulus of continuity; if that were the case, then the Mandelbrot set would be locally connected, which would indeed be a breakthrough.  So I rather think that that problem is open.

Looking up the Yampolsky and Braverman book is a good idea in any case.