Monday 11 June 2012

P vs NP. A big Problem?


I have just been reading write up’s about a new film. The subject is perhaps not on the usual list of things we see the cinema.
http://www.travellingsalesmanmovie.com/

Complex math problems are probably near the bottom of things that people get excited about. But Travelling Salesman might just change that. The film is an, “intellectual thriller" about four mathematicians hired by the U.S. government to solve the biggest unsolved problem in computer science. Four people have jointly created a ‘system’ which means major advancement for civilisation or the destruction of humanity.
The P vs NP problem lies unsolved despite a $1 million bounty.  The problem is whether the P and NP classes are actually identical. Most researchers believe they are not.   It seems that we live in a world where some problems are fundamentally harder than others (or impossible).
Travelling Salesman takes place in a  world where Horton and colleagues prove that P = NP, This means that they can solve a range of incredibly difficult real-world problems from gene sequencing to the “travelling salesman” problem, crucial for logistics and scheduling.

According to the New Scientist article the plot unfolds after we learn that the solution enables the mathematicians to crack any cryptography system in the world, which is why their four-year research project has been funded to the tune of millions of dollars by the US government.
This was interesting as it follows on from another article in the New Scientist about Alan Turing. He invented the computer while trying to solve the above fundamental mathematical problem. By building his machine, he demonstrated that mathematics wasn't as perfect as many at the time believed, while also showing how powerful a computer could be.

Alan Turing, was one of the 20th century's most wide-ranging and original minds, and was born 100 years ago. In the New Scientist there is an article by John Graham-Cumming explaining why his ideas still matter now. Turing essentially founded computer science, helped the Allies win the Second World War with hard work and a succession of insights, asked fundamental questions about the nature of intelligence and its link with the brain's structure, and laid the foundations for an area of biology that is only now being fully appreciated and researched. I Blogged a bit about him before.

1 comment: