Complexity of a variant of the Mandelbrot set decision problem? - MathOverflow 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 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>