Thursday, September 16, 2010

A candidate NP-complete problem related to Mandelbrot set

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