Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a modified version of a question posted on StackExchange TCS.

Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define

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

where $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.

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

EDIT: Is there any NP-complete problem related to Mandelbrot set?

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.