most recent 30 from http://mathoverflow.net 2013-05-19T22:26:29Z http://mathoverflow.net/feeds/question/40169 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40169/complexity-of-a-variant-of-the-mandelbrot-set-decision-problem Mohammad Al-Turkistany 2010-09-27T15:54:12Z 2010-09-30T13:42:35Z

<p>This is a modified version of a question posted on <a href="http://cstheory.stackexchange.com/questions/778" rel="nofollow">StackExchange TCS.</a> <a href="http://cstheory.stackexchange.com/questions/778" rel="nofollow"></a></p> <p>Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define</p> <p>$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$}</p> <p>where $r$ is real number and $k$ is an integer in unary.</p> <p>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.</p> <blockquote> <p>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 ?</p> </blockquote> <p><strong>EDIT:</strong> Is there any NP-complete problem related to Mandelbrot set?</p>