Complexity of a variant of the Mandelbrot set decision problem?

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 1

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.

Answer 2

This answer combines some of my comments to the question and improves them.

The set M is decidable in linear time on a Turing machine over the reals.

Here is why. The definition of the set M in the question consists of two conditions, but note that the first condition is redundant: it is well-known that the infinite sequence P_c(0), P_c(P_c(0)), P_c(P_c(P_c(0))), … is unbounded if it contains a term whose absolute value is greater than 2. Therefore, to decide whether a given pair (c,k) belongs to the set M or not, we only have to test the second condition, which can be done in O(k) time on a Turing machine over the reals. Since k is given in unary, this is linear time in the input length.

I do not know much about Turing machines over the reals, and I may have made any mistakes.

Answer 3

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