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

No comments:

Post a Comment