Question: 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, "<" 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**

Answer: 
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.
This problem related to Mandelbrot set seems to be $NP$-complete:

$M=${$(c,k,r) |$ In the sequence $P\_c (0),P\_c (P\_c (0)), P\_c (P\_c (P\_c (0)))...$ of first $k$ complex numbers, there is a subset $T$ of complex numbers such that the sum of the real parts $\gt$ $r.k$ and the sum of imaginary parts $\gt$ $r.k$}

$r$ is real number and $k$ is an integer in unary.

Here is a geometric interpretation, since each $P\_c^i(0)$ is a vector in 2D, we want to find the maximum size square obtainable by the summation of a subset of two dimensional vectors.

A promising reduction is from (optimization) number partition problem where each partition has the same number of elements (in the optimization version, we minimize the difference between the two sums).