Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Mark Braverman and Michael Yampolsky's book "The Computability of Julia Sets" may be of interest to you. –  matus Aug 30 '10 at 22:50
    
Are we restricting our attention to rational complex numbers that are members of M? –  Emil Aug 30 '10 at 23:59
1  
@Tsuyoshi, Use The Blum-Shub-Smale Model, (algebraic TM) –  Mohammad Al-Turkistany Aug 31 '10 at 0:59
1  
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 Aug 31 '10 at 11:42
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. –  Emil Sep 9 '10 at 18:55

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer
    
@Tsuyoshi, Don't jump into conclusions, Did you try to count the number of multiplications and additions after K iterations? –  Mohammad Al-Turkistany Aug 31 '10 at 18:05
    
@Tsuyoshi, What is the run-time after K iterations? (Write it as summation and choose any complex number C) –  Mohammad Al-Turkistany Aug 31 '10 at 18:13
1  
@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 Aug 31 '10 at 19:51
1  
@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 Aug 31 '10 at 21:32
1  
@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 Sep 1 '10 at 1:01

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.