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

Sunday, August 15, 2010

My criteria for what I consider a serious proof for the P vs NP problem

In light of Deolalikar's proof for P!=NP , Any valid resolution of the P vs NP problem must shed light and offer new insights into some of the fundamental concepts in mathematics and computer science. We want to really understand the true relationship between concepts like efficient computation of functions, randomness, and the computational nature of proofs. Why are some functions hard to compute while others are easy? What does constitute a random function? The ultimate resolution of the P vs NP problem must provide new insights into the nature of randomness and how it relates to efficient computation.

In my opinion, what is needed is a paradigm shift. This is what the history of scientific revolutions taught us. I believe we need to abandon the tradition of using polynomial functions to define the various notions of efficient computation. Invoking polynomial growth rates could be a symptom of paradigm blindness. I call it the Polynomial Disease.