Andrew Prendergast

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.

Posted by ap at 01:33 PM | Permalink | Comments (1)

Yay the DARPA grand challenge is on again.

This year the course is a simulated city environment.

The competition, slated to take place in an undisclosed location in November 2007, is supported by the Pentagon's Defense Advanced Research Projects Agency to spur development of military vehicles that could fight in war zones without any sort of remote control.

The robotic vehicles will have to navigate a complex 60-mile test course designed like a real city street filled with moving manned and unmanned vehicles. Participants will be tested on how well they make sharp turns, navigate traffic circles and avoid obstacles such as utility poles, trees and parked cars. The vehicles will also have to obey traffic laws, change lanes, merge with moving cars and pull into a parking lot using only their computer brain and sensors.

The first vehicle that successfully completes the mission in less than six hours will win $2 million. Second-place finishers will get $500,000 while third place will receive $250,000.

Posted by ap at 08:17 PM | Permalink | Comments (0)