<p>Let's look at $M$ for fixed $k$ first.</p>

<p>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$.</p>

<p>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'].</p>

<p>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.</p>

<p>Looking up the Yampolsky and Braverman book is a good idea in any case.</p>

CC BY-SA 2.5
2010-08-30T23:54:21.863Z
2010-08-30T23:54:21.863Z
Jacques Carette
<p>This answer combines some of my comments to the question and improves them.</p>

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

<p>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<sub>c</sub>(0), P<sub>c</sub>(P<sub>c</sub>(0)), P<sub>c</sub>(P<sub>c</sub>(P<sub>c</sub>(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.</p>

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

CC BY-SA 2.5
2010-08-31T18:05:53.503Z
@Tsuyoshi, Don't jump into conclusions, Did you try to count the number of multiplications and additions after K iterations?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-31T18:13:15.190Z
@Tsuyoshi, What is the run-time after K iterations? (Write it as summation and choose any complex number C)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-31T18:56:30.650Z
@turkistany: By definition, P_c(z) can be computed from c and z by using one multiplication and one addition of complex numbers.  Note that an arithmetic operation on complex numbers can be simulated by O(1) arithmetic operations on real numbers and that every arithmetic operation on reals takes O(1) time on a Turing machine on the reals by the definition of Turing machines on the reals.  Therefore, the total time of k iterations is O(k), which is linear in the input length.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T19:51:51.513Z
@turkistany: It occurred to me that for some reason you might be considering about expanding the polynomial P_c(…(P_c(0))…) into the form ∑_{i=0}^{2^k} α_i c^i.  Needless to say, this polynomial becomes more difficult to handle if you expand it.  The point is that you do not have to expand the polynomial in order to decide whether a given pair (c,k) belongs to your set M on a Turing machine over the reals.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T20:03:28.467Z
@Tsuyoshi, OK, after k iterations and you found that the complex magnitude is less than 2, Can you conclude that the infinite sequence of iterations is bounded? Is the corresponding (c,k) in M or not?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-31T21:19:30.783Z
@turkistany: Please understand what your own definition of the set M says.  If |z| does not exceed 2 within the first k iterations, then the pair (c,k) is not in M (because the second condition fails), no matter whether the infinite sequence is bounded or not.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T21:32:49.997Z
@turkistany: By the way, you asked a question about the running time of k iterations without telling me your intent, and I answered it.  You asked me another question and I answered it.  I would like to let you know that I am getting tired of this seemingly fruitless interaction.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T21:56:45.687Z
I changed the description of the “algorithm” a little bit.  This does not answer the questions which the questioner asked in the comments, but hopefully it avoids some potential confusion.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T22:59:21.873Z
@Tsuyoshi, you did not understand the definition, It is asking  whether the the sequence is UNBOUNDED such that breakaway occurs at an iteration less than K. Please compare it to the bounded Halting problem where we do not know when the Turing machine is going to halt. Here we do not know when the breakaway will occur.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-31T23:21:50.130Z
To make it clear, I will include this comment in the problem description.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-01T00:37:15.243Z
@turkistany: I have never misunderstood your definition of the set M.  The first condition is redundant because it is implied by the second condition, as I wrote in my answer (revision 2).  I really do not know how to convince you, though.  I guess that I have done my best to try to convince you.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-01T00:44:16.447Z
@Tsuyoshi, the problem is not about decidability, if it was then your right. The question is about how fast the sequence is going to breakaway from the disk of radius 2. I hope it is clear.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-01T01:01:49.130Z
@turkistany: “The question is about how fast the sequence is going to breakaway from the disk of radius 2.”  The question as is written (even the newest revision, revision 7) is not about that.  If that was your intent, you stated the question incorrectly.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-10T00:54:36.297Z
This answer no longer applies to the question because the question was modified significantly in revision 9.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T11:03:56.553Z
2010-09-09T16:14:36.397Z
2010-09-09T16:14:36.397Z
Tsuyoshi Ito
<p>This problem related to Mandelbrot set seems to be $NP$-complete:</p>

<p>$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$}</p>

<p>$r$ is real number and $k$ is an integer in unary.</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-09-11T16:42:12.717Z
2010-09-16T04:36:29.127Z
2010-09-16T04:36:29.127Z
Mohammad Al-Turkistany
<p>Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$  where $c$ is a complex number</p>

<p>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$}</p>

<p>Assume $k$ and $m$ are integers given in unary encoding</p>

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

<p>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.</p>

<p><strong>UPDATE:</strong> The problem is in $NP$ since there is a polynomially verifiable certificate of membership.</p>

<blockquote>
  <p>So, Is there an efficient algorithm or is it $NP$-hard to decide set $M$?</p>
</blockquote>

<p><strong>The problem went through major changes for these reasons:</strong></p>

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

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

<p><strong>Also, the bounty may be awarded to the first person who poses an $NP$-complete problem related to Mandelbrot Set</strong> </p>

CC BY-SA 2.5
2010-08-30T22:50:50.957Z
Mark Braverman and Michael Yampolsky's book "The Computability of Julia Sets" may be of interest to you.
matus
CC BY-SA 2.5
2010-08-30T23:59:08.787Z
Are we restricting our attention to rational complex numbers that are members of M?
Emil
CC BY-SA 2.5
2010-08-31T00:05:32.843Z
Why is this tagged "np-completeness"?
Emil
CC BY-SA 2.5
2010-08-31T00:28:34.410Z
@Emil, the problem is defined over **C** , (complex numbers)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-31T00:41:11.660Z
How is the complex number c given to the Turing machine?  Are you considering in terms of Turing machines over real/complex numbers?
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T00:59:55.320Z
@Tsuyoshi, Use The Blum-Shub-Smale Model, (algebraic TM)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-31T01:03:26.203Z
I guess that it is better to state it in the question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T01:17:12.610Z
I do not know much about Turing machines over the reals/complexes, but it seems to me that the straightforward implementation of the definition of M gives you an O(k)-time algorithm on a Turing machine over the reals, putting the problem into P over ℝ.  Am I missing something?
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T02:22:11.813Z
@Tsuyoshi: Sure, each slice of M for fixed k, in the BSS model will be decidable in O(k) time, but what about all of M?
Jacques Carette
CC BY-SA 2.5
2010-08-31T02:22:48.623Z
@turkistany: why did you define the complement of the Mandelbrot set as M ?
Jacques Carette
CC BY-SA 2.5
2010-08-31T02:46:49.353Z
@Jacques: I think that the whole M is decidable in time linear in the input size, since the input size is at least k (because k is given in unary).  Also, M itself is not the complement of the Mandelbrot set; the projection of M to the first coordinate is the complement of the Mandelbrot set.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T02:57:01.673Z
Contrary to the title of the question, the set M in the question is very different from the Mandelbrot set, and the complexity of M seems to have almost nothing to do with the decidability/complexity of the Mandelbrot set, except that writing the Mandelbrot set as the complement of the projection of M shows that the complement of the Mandelbrot set is recursively enumerable on a Turing machine over the reals.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T03:50:02.607Z
@Tsuyoshi: you are correct that M is the union of the level sets of the 'outside' of the Mandelbrot set.  And yes, the complement of M is indeed recursively enumerable, even over the usual binary model.  The OP was about 'finer' complexity questions than that.
Jacques Carette
CC BY-SA 2.5
2010-08-31T10:54:22.370Z
@Jacques: My point is that the question is not about the Mandelbrot set, contrary to the original title, and the set M is decidable in linear time, period.  “The OP was about 'finer' complexity questions than that.”  Well, if you believe that the question is about the decidability/complexity of the Mandelbrot set, it is fine with me.  In fact, that is a more interesting question.  But at least that is not the question as it is.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T11:09:08.137Z
@Jacques: “complement of M is indeed recursively enumerable”  I did not say that.  Please understand the difference between the set M in the question and the Mandelbrot set.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T11:42:16.340Z
I think we need to rename the set M, as M is commonly used to denote the Mandelbrot set, not its complement. Or - rewrite the question to be about the Mandelbrot set, which would be more interesting (and probably undecidable).
Emil
CC BY-SA 2.5
2010-08-31T12:43:51.760Z
@Tsuyoshi: M is the disjoint union of the level set approximations to the complement of the Mandelbrot set.  Or at least that is how I read it.  Do you read it differently?
Jacques Carette
CC BY-SA 2.5
2010-08-31T12:59:05.243Z
@Jacques: “M is the disjoint union of the level set approximations to the complement of the Mandelbrot set.”  Yes, if by disjoint union you mean discriminated union (“disjoint union” sometimes means the usual union of pairwise disjoint sets, and I want to avoid this ambiguity).  Have I ever suggested otherwise?
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T12:59:28.827Z
@Jacques: And I still do not know why you commented as if I had said that the complement of M is recursively enumerable (well, it is true because M is linear-time decidable, but it is missing the point).  The only thing I said about recursive enumerability is that the complement of the Mandelbrot set (not of M) is r.e. on a Turing machine over the reals.  This made me suspect that you were still confusing the set M in the question with the Mandelbrot set.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T14:57:44.013Z
@Tsuyoshi: re defn - no, you did not, but I was starting to wonder how far apart our understanding was (I think it is rapidly converging).  And the other comment about recursive enumerability is probably my misinterpretation of what you said, sorry.
Jacques Carette
CC BY-SA 2.5
2010-08-31T15:50:31.350Z
I voted the question down.  Although a high-level, vague question “What is the complexity of the Mandelbrot set?” could have become an interesting concrete question if formulated carefully, the questioner somehow chose an uninteresting formulation.  The question is trivial once you understand the question, and its only difficulty lies in understanding the confusing notation.  In my humble opinion, if anyone is interested in other aspects of the complexity of the Mandelbrot set which are not answered in this question, he/she should ask a separate question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-31T17:40:14.587Z
@Tsuyoshi, Don't jump into conclusions, Did you try to count the number of multiplications and additions after K iterations?.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-31T17:55:54.257Z
@turkistany: Yes, I did.  If you have a further question about my answer, please attach a comment to my answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-01T00:43:23.103Z
@Tsuyoshi, the problem is not about decidability, if it was then your right. The question is about how fast the sequence is going to breakaway from the disk of radius 2. I hope it is clear.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-09T18:54:12.047Z
I don't believe that the problem is in NP. Leaving aside the fact that we are dealing with "real" Turing machines and not Turing machines, I don't think there is a polynomial certificate of membership.
Emil
CC BY-SA 2.5
2010-09-09T18:55:16.303Z
Also, I do not feel that questions should be edited so they are quite different to the one originally asked. This is not what the edit feature is for! A new question would be better.
Emil
CC BY-SA 2.5
2010-09-09T20:08:58.707Z
@Emil, there is certificate $n$ in unary for the complement of M (the number of iterations at the breakaway point)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-09T23:28:19.727Z
Well n is not a certificate, and it is not necessarily bounded by a polynomial in k.
Emil
<cc.complexity-theory><ds.algorithms><computing-over-reals><mandelbrot>
Complexity of a variant of the Mandelbrot set decision problem?
Mohammad Al-Turkistany
# Complexity of a variant of the Mandelbrot set decision problem?

(Asked by: username_0 on 2010-08-30)

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**

**Tags:** cc.complexity-theory, ds.algorithms, computing-over-reals, mandelbrot
> **Comments:**
> **username_1**: Mark Braverman and Michael Yampolsky's book "The Computability of Julia Sets" may be of interest to you.  
> **username_2**: Are we restricting our attention to rational complex numbers that are members of M?  
> **username_2**: Why is this tagged "np-completeness"?  
> **username_0**: @Emil, the problem is defined over **C** , (complex numbers)  
> **username_3**: How is the complex number c given to the Turing machine?  Are you considering in terms of Turing machines over real/complex numbers?  
> **username_0**: @Tsuyoshi, Use The Blum-Shub-Smale Model, (algebraic TM)  
> **username_3**: I guess that it is better to state it in the question.  
> **username_3**: I do not know much about Turing machines over the reals/complexes, but it seems to me that the straightforward implementation of the definition of M gives you an O(k)-time algorithm on a Turing machine over the reals, putting the problem into P over ℝ.  Am I missing something?  
> **username_4**: @Tsuyoshi: Sure, each slice of M for fixed k, in the BSS model will be decidable in O(k) time, but what about all of M?  
> **username_4**: @turkistany: why did you define the complement of the Mandelbrot set as M ?  
> **username_3**: @Jacques: I think that the whole M is decidable in time linear in the input size, since the input size is at least k (because k is given in unary).  Also, M itself is not the complement of the Mandelbrot set; the projection of M to the first coordinate is the complement of the Mandelbrot set.  
> **username_3**: Contrary to the title of the question, the set M in the question is very different from the Mandelbrot set, and the complexity of M seems to have almost nothing to do with the decidability/complexity of the Mandelbrot set, except that writing the Mandelbrot set as the complement of the projection of M shows that the complement of the Mandelbrot set is recursively enumerable on a Turing machine over the reals.  
> **username_4**: @Tsuyoshi: you are correct that M is the union of the level sets of the 'outside' of the Mandelbrot set.  And yes, the complement of M is indeed recursively enumerable, even over the usual binary model.  The OP was about 'finer' complexity questions than that.  
> **username_3**: @Jacques: My point is that the question is not about the Mandelbrot set, contrary to the original title, and the set M is decidable in linear time, period.  “The OP was about 'finer' complexity questions than that.”  Well, if you believe that the question is about the decidability/complexity of the Mandelbrot set, it is fine with me.  In fact, that is a more interesting question.  But at least that is not the question as it is.  
> **username_3**: @Jacques: “complement of M is indeed recursively enumerable”  I did not say that.  Please understand the difference between the set M in the question and the Mandelbrot set.  
> **username_2**: I think we need to rename the set M, as M is commonly used to denote the Mandelbrot set, not its complement. Or - rewrite the question to be about the Mandelbrot set, which would be more interesting (and probably undecidable).  
> **username_4**: @Tsuyoshi: M is the disjoint union of the level set approximations to the complement of the Mandelbrot set.  Or at least that is how I read it.  Do you read it differently?  
> **username_3**: @Jacques: “M is the disjoint union of the level set approximations to the complement of the Mandelbrot set.”  Yes, if by disjoint union you mean discriminated union (“disjoint union” sometimes means the usual union of pairwise disjoint sets, and I want to avoid this ambiguity).  Have I ever suggested otherwise?  
> **username_3**: @Jacques: And I still do not know why you commented as if I had said that the complement of M is recursively enumerable (well, it is true because M is linear-time decidable, but it is missing the point).  The only thing I said about recursive enumerability is that the complement of the Mandelbrot set (not of M) is r.e. on a Turing machine over the reals.  This made me suspect that you were still confusing the set M in the question with the Mandelbrot set.  
> **username_4**: @Tsuyoshi: re defn - no, you did not, but I was starting to wonder how far apart our understanding was (I think it is rapidly converging).  And the other comment about recursive enumerability is probably my misinterpretation of what you said, sorry.  
> **username_3**: I voted the question down.  Although a high-level, vague question “What is the complexity of the Mandelbrot set?” could have become an interesting concrete question if formulated carefully, the questioner somehow chose an uninteresting formulation.  The question is trivial once you understand the question, and its only difficulty lies in understanding the confusing notation.  In my humble opinion, if anyone is interested in other aspects of the complexity of the Mandelbrot set which are not answered in this question, he/she should ask a separate question.  
> **username_0**: @Tsuyoshi, Don't jump into conclusions, Did you try to count the number of multiplications and additions after K iterations?.  
> **username_3**: @turkistany: Yes, I did.  If you have a further question about my answer, please attach a comment to my answer.  
> **username_0**: @Tsuyoshi, the problem is not about decidability, if it was then your right. The question is about how fast the sequence is going to breakaway from the disk of radius 2. I hope it is clear.  
> **username_2**: I don't believe that the problem is in NP. Leaving aside the fact that we are dealing with "real" Turing machines and not Turing machines, I don't think there is a polynomial certificate of membership.  
> **username_2**: Also, I do not feel that questions should be edited so they are quite different to the one originally asked. This is not what the edit feature is for! A new question would be better.  
> **username_0**: @Emil, there is certificate $n$ in unary for the complement of M (the number of iterations at the breakaway point)  
> **username_2**: Well n is not a certificate, and it is not necessarily bounded by a polynomial in k.  

---

## 3 answers

### Answer by username_4 on 2010-08-30. Score: 8

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 by username_3 on 2010-08-31. Score: 5

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 Pc(0), Pc(Pc(0)), Pc(Pc(Pc(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.

> **Comments:**
> **username_0**: @Tsuyoshi, Don't jump into conclusions, Did you try to count the number of multiplications and additions after K iterations?  
> **username_0**: @Tsuyoshi, What is the run-time after K iterations? (Write it as summation and choose any complex number C)  
> **username_3**: @turkistany: By definition, P_c(z) can be computed from c and z by using one multiplication and one addition of complex numbers.  Note that an arithmetic operation on complex numbers can be simulated by O(1) arithmetic operations on real numbers and that every arithmetic operation on reals takes O(1) time on a Turing machine on the reals by the definition of Turing machines on the reals.  Therefore, the total time of k iterations is O(k), which is linear in the input length.  
> **username_3**: @turkistany: It occurred to me that for some reason you might be considering about expanding the polynomial P_c(…(P_c(0))…) into the form ∑_{i=0}^{2^k} α_i c^i.  Needless to say, this polynomial becomes more difficult to handle if you expand it.  The point is that you do not have to expand the polynomial in order to decide whether a given pair (c,k) belongs to your set M on a Turing machine over the reals.  
> **username_0**: @Tsuyoshi, OK, after k iterations and you found that the complex magnitude is less than 2, Can you conclude that the infinite sequence of iterations is bounded? Is the corresponding (c,k) in M or not?  
> **username_3**: @turkistany: Please understand what your own definition of the set M says.  If |z| does not exceed 2 within the first k iterations, then the pair (c,k) is not in M (because the second condition fails), no matter whether the infinite sequence is bounded or not.  
> **username_3**: @turkistany: By the way, you asked a question about the running time of k iterations without telling me your intent, and I answered it.  You asked me another question and I answered it.  I would like to let you know that I am getting tired of this seemingly fruitless interaction.  
> **username_3**: I changed the description of the “algorithm” a little bit.  This does not answer the questions which the questioner asked in the comments, but hopefully it avoids some potential confusion.  
> **username_0**: @Tsuyoshi, you did not understand the definition, It is asking  whether the the sequence is UNBOUNDED such that breakaway occurs at an iteration less than K. Please compare it to the bounded Halting problem where we do not know when the Turing machine is going to halt. Here we do not know when the breakaway will occur.  
> **username_0**: To make it clear, I will include this comment in the problem description.  
> **username_3**: @turkistany: I have never misunderstood your definition of the set M.  The first condition is redundant because it is implied by the second condition, as I wrote in my answer (revision 2).  I really do not know how to convince you, though.  I guess that I have done my best to try to convince you.  
> **username_0**: @Tsuyoshi, the problem is not about decidability, if it was then your right. The question is about how fast the sequence is going to breakaway from the disk of radius 2. I hope it is clear.  
> **username_3**: @turkistany: “The question is about how fast the sequence is going to breakaway from the disk of radius 2.”  The question as is written (even the newest revision, revision 7) is not about that.  If that was your intent, you stated the question incorrectly.  
> **username_3**: This answer no longer applies to the question because the question was modified significantly in revision 9.  

---

### Answer by username_0 on 2010-09-11. Score: 1

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


---

