Can there be an algorithm for every human desire?

Share via AddThis
Posted March 26, 2013

Golden-Ticket[1]

The travelling salesman problem still defies the most powerful computers (Image: Quentin Bertoux/Agence Vu)

Lance Fortnow shows how an esoteric mathematical problem has deep implications for our future in The Golden Ticket: P, NP, and the search for the impossible.

It seems as if computers can do almost anything. Serve up the world’s knowledge in an instant? No problem. Simulate a human brain? Working on it.

But are there some tasks that computers will never be able to perform, no matter how powerful they become? This question forms the basis of one of the most important problems in computer science and mathematics, known by the esoteric name: P versus NP.

The definition of this problem is tricky and technical, but in The Golden Ticket, Lance Fortnow cleverly sidesteps the issue with a boiled-down version. P is the collection of problems we can solve quickly, NP is the collection of problems we would like to solve. If P = NP, computers can answer all the questions we pose and our world is changed forever.

Read more at: NewScientist.com



54,130 science & technology articles

Categories

Our Articles (see all)

General News

Follow us

Facebook   Twitter   Pinterest   StumbleUpon   Plurk
Google+   Tumblr   Delicious   RSS   Newsletter via Email

Featured Video (see all)


Using static electricity, insect-sized flying robots can land and stick to surfaces
Small drones need to stay aloft do their jobs — whether that’s searching for dangerous gas leaks or…

Featured Image (see all)

NASA’s rodent habitat, developed at Ames Research Center in Moffett Field, California, serves as a home away from home for mice on the International Space Station. Previous rodent experiments aboard space shuttles contributed to the development of new drugs now fighting osteoporosis on Earth.

Credits: NASA
Mice Studies in Space Offer Clues on Bone Loss
Astronauts know their bodies will be tested during time spent on the International Space Station, from the 15…