Slashdot Mirror
Travelling Salesman, Thriller Set In a World Where P=NP
mikejuk writes with this excerpt from I Programmer: "A movie that features science and technology is always welcome, but is it not often we have one that focuses on computer science. Travelling Salesman is just such a rare movie. As you can guess from its name, it is about the Travelling Salesman problem, more precisely about the P=NP question. Written and directed by Timothy Lanzone, and produced by Fretboard Pictures, it should premiere on June 16. As the blurb to the movie trailer says: 'Travelling Salesman is an intellectual thriller about four of the world's smartest mathematicians hired by the U.S. government to solve the most elusive problem in computer science history — P vs. NP. The four have jointly created a "system" which could be the next major advancement for humanity or the downfall of society.'"
The trailer is:
"In a world where P = NP... cryptography becomes meaningless."
If you didn't hear that in Don LaFontaine's voice you are a bad person.
I'm a good cook. I'm a fantastic eater. - Steven Brust
http://www.travellingsalesmanmovie.com/
It's uncertain what complexity class factorization in, but the best known techniques are not in P. P=NP therefore implies there is indeed a 'better' factorization algorithm. And so, you can crack encryption faster.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
Factoring is NP, since we can verify the results in polynomial time. It's not NP-complete, so finding a polynomial algorithm for factoring doesn't necesarily mean that there's one for 3-SAT or TSP, but if we find a polynomial algorithm for TSP, then there is one for factoring.