MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Question

2 improved formatting

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?

1

# Complexity of a variant of the Mandelbrot set decision problem?

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 ?