Travelling Salesman is an intellectual thriller about four 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 our civilization or destroy the fabric of humanity.
The solution’s immediate application would be for theoretical computer science. However, its application would soon extend to countless other disciplines. For example, by utilizing the solution to P vs. NP, a hacker could crack advanced encryption codes within seconds—a task that now takes weeks, months, or even years. He could break into La Guardia's air traffic control or China’s communication grid. But the mathematical algorithm would also serve as the basis for accelerated biological research, curing diseases such as AIDS and cancer.
The film begins with the four at a secret location waiting to meet with a high-ranking official of the United States Department of Defense. The group discusses the global implications of their solution, and they agree that they must be extremely careful with who they allow to control their discovery.
The silver-tongued DoD agent soon arrives and presents them each with an offer of 10 million dollars in exchange for their portion of the algorithmic solution. He attempts to deftly address their concerns and sway the opinions of the four.
In the end, only one mathematician speaks out against selling the solution. In pleading his case, he is forced to reveal the dark truth about his portion of the algorithm. As the mathematicians are about to sign documents that will give the U.S. government sole and private ownership of their solution, they wrestle with the moral dilemma of how this volatile discovery will be used. The math is real. The implications are real.
The math behind the film
The P vs. NP problem is the most notorious unsolved problem in computer science. First introduced in 1971, it asks whether one class of problems (NP) is more difficult than another class (P).
Mathematicians group problems into classes based on how long they take to be solved and verified. “NP” is the class of problems whose answer can be verified in a reasonable amount of time. Some NP problems can also be solved quickly. Those problems are said to be in “P”, which stands for polynomial time. However, there are other problems in NP which have never been solved in polynomial time.
The question is, is it possible to solve all NP problems as quickly as P problems? To date, no one knows for sure. Some NP questions seem harder than P questions, but they may not be.
Currently, many NP problems take a long time to solve. As such, certain problems like logistics scheduling and protein structure prediction are very difficult. Likewise, many cryptosystems, which are used to secure the world's data, rely on the assumption that they cannot be solved in polynomial time.
If someone were to show that NP problems were not difficult—that P and NP problems were the same—it would would have significant practical consequences. Advances in bioinformatics and theoretical chemistry could be made. Much of modern cryptography would be rendered inert. Financial systems would be exposed, leaving the entire Western economy vulnerable.
Proving that P = NP would have enormous ramifications that would be equally enlightening, devastating, and valuable...
Thanks, Akito.
The solution’s immediate application would be for theoretical computer science. However, its application would soon extend to countless other disciplines. For example, by utilizing the solution to P vs. NP, a hacker could crack advanced encryption codes within seconds—a task that now takes weeks, months, or even years. He could break into La Guardia's air traffic control or China’s communication grid. But the mathematical algorithm would also serve as the basis for accelerated biological research, curing diseases such as AIDS and cancer.
The film begins with the four at a secret location waiting to meet with a high-ranking official of the United States Department of Defense. The group discusses the global implications of their solution, and they agree that they must be extremely careful with who they allow to control their discovery.
The silver-tongued DoD agent soon arrives and presents them each with an offer of 10 million dollars in exchange for their portion of the algorithmic solution. He attempts to deftly address their concerns and sway the opinions of the four.
In the end, only one mathematician speaks out against selling the solution. In pleading his case, he is forced to reveal the dark truth about his portion of the algorithm. As the mathematicians are about to sign documents that will give the U.S. government sole and private ownership of their solution, they wrestle with the moral dilemma of how this volatile discovery will be used. The math is real. The implications are real.
The math behind the film
The P vs. NP problem is the most notorious unsolved problem in computer science. First introduced in 1971, it asks whether one class of problems (NP) is more difficult than another class (P).
Mathematicians group problems into classes based on how long they take to be solved and verified. “NP” is the class of problems whose answer can be verified in a reasonable amount of time. Some NP problems can also be solved quickly. Those problems are said to be in “P”, which stands for polynomial time. However, there are other problems in NP which have never been solved in polynomial time.
The question is, is it possible to solve all NP problems as quickly as P problems? To date, no one knows for sure. Some NP questions seem harder than P questions, but they may not be.
Currently, many NP problems take a long time to solve. As such, certain problems like logistics scheduling and protein structure prediction are very difficult. Likewise, many cryptosystems, which are used to secure the world's data, rely on the assumption that they cannot be solved in polynomial time.
If someone were to show that NP problems were not difficult—that P and NP problems were the same—it would would have significant practical consequences. Advances in bioinformatics and theoretical chemistry could be made. Much of modern cryptography would be rendered inert. Financial systems would be exposed, leaving the entire Western economy vulnerable.
Proving that P = NP would have enormous ramifications that would be equally enlightening, devastating, and valuable...
Thanks, Akito.
0 comments :
Post a Comment