solving the uNPsolvable?
Some startup is launching a new chip tomorrow. It makes the huge claim of being able to solve an NP-complete problem. They chose a great venue - the Computer History Museum in Silicon Valley, just around the corner from the Googleplex.
Lots of computing problems are NP, generally most of the good ones. The 25 word summary is that NP problems can not currently be solved in a reasonable amount of time except when the problem is reduced to a trivial size. An example of an NP-complete problem is finding the optimal route a FedEx truck should take. Fortunately for most of these problems, fast estimations do exist.
Where NP-completeness gets interseting is that if you can solve any single NP-complete problem (such as the fedex problem), you can use that same solution to solve every other NP-complete problem - ie, solve one and you have solved them all.
If they are for real then then implications are huge, from breaking encryption to achieving artificial intelligence. I am optimistically sceptical.. lets see what happens.
ap.
Comments
Hey AP,
Good blog, but too geeky for a ludite like me. Sounds as if you are studying (where) and bad news about your cat (Winnie is still going strong). Will be in Melb on business at the start of April if you have time to catch up?
Posted by: Richard taylor | March 15, 2007 06:18 PM