Thursday, January 20, 2011

P=NP, the next try

It could be hot, if it were correct. Now, it has to survive the scrutiny of mathematicians and theoretical computer sciencists from all over the world: Vladimir Romanov has published in his blog and on the arXiv a manuscript with an (as he says) polynomial-time (i.e. "fast") algorithm for the so-called 3-SAT problem from theoretical computer science. Now, that particular problem is known to be one of the class of NP-complete problems, and if any NP-complete problem can be solved in poly-time, then all NP problems (these are "hard ones") can be, i.e. P=NP with P as the set of problems solvable in poly-time. This may sound pretty exotic, but it has enough interesting consequences to make P?=NP one of the fundamental Millenium Prize Problems of the Clay Institute. Interesting times and a potential $1.000.000 bounty ahead...

No comments:

Post a Comment