If it's anything like Deception Point, I'll be staying well clear of it. Typically, stories in that genre use compsci-babble as smoke and mirrors to cover up the lack of storyline.
I know what I'd do if I alone knew the solution to the TSP: I'd become a traveling salesman. Or, perhaps, I'd start a business that employs traveling salesmen and use the efficiency gains to amass dazzling wealth and power.
One of the clearest examples I’ve seen of HTML5 Animation maturing. I had to right-click to check whether it was done in Flash. The site even comes with a splash screen and a ‘Skip intro’ button. The horizontal scrollbars down the middle of the page and the Mystery Meat navigation feel very authentic. I love how the actual content is placed in lightboxes, making very little use of the available space. The barely legible 90s techno fonts really finished the look. Bravo!
I love hypothetical science fiction movies like this, but they so often get criticized for the improbability of their premise rather than admired for their vision.
Many do manage to express their vision well enough to rise above their improbability. Primer, Source Code, Cube, plenty of others are utterly implausible yet garnered praise.
GAs are not the best approach even for randomized heuristic approximations. Mostly they are cute, biologically intriguing programming exercises for people that don't care about sitting down and formally working out the specifications of a serious optimization problem. Often they end up throwing many CPU-hours at a relatively simple problem that they weren't even looking to solve, and get a sub-optimal solution because they didn't even bother to optimize the learning/mutation schedule, which would speed it up by an order of magnitude, but that would require maths and thinking, instead of just throwing more randomness against the wall because "it's evolution".
Genetic Algorithms aren't even easier to implement than other randomized heuristic approximations. For instance, Simulated Annealing is basically (but not quite) a GA with a population of one, so you don't need selection or crossover (do you use tournament selection or roulette selection? does it matter? will you try both? what will be your population size?). Simulated Annealing is much easier to implement and has fewer variables to optimize (such as the cooling/learning schedule). Of course it's not nearly as "sexy" as the biologically inspired genetic algorithm.
Most importantly however, a GA does not solve P?=NP, so it is not sufficient for the premise to this movie, which is about the consequences of solving P?=NP, not about arriving at suboptimal but perhaps sufficient solution in almost reasonable time to a TSP problem that doesn't actually have a practical use.
Sufficient for any practical use is not "solved" in the mathematical sense.
Also, AFAIK, a general solution to P=NP could still be very time consuming to calculate (even if you prove polynomial time solutions, that could still be a very high order polynomial). That is, your general solution to the problem could be only slightly better than O(n!) and satisfy.
I'll be honest, this looks comically bad and has no merit besides the fact that it has a geeky premise.
I'm sure the underlying discussion of "What if P=NP? is solved?" is incredibly interesting but what I got from the trailer was that this was a movie with a bad script, bad cinematography, bad acting, and bad editing.
I'm hesitant to totally dismiss the movie, but the trailer definitely left me cold. In addition to all the problems you mentioned, I feel like they blew the "____ simplified" gimmick, which almost worked to tie the trailer together.
In some ways the trailer reminded me of Primer but it didn't quite make the low-budget vibe work in it's favor. Having made a few student films, but never having made a good short film, it's still hard for me to put my finger on the little differences that make something like this work.
Delivery. The trailer lost me when the characters were just actors delivering lines; characters in Primer came across as speaking for real. Such a little difference, but one that makes it work.
The movie doesn't do much for me, but I can't wait for the trailer with the gravelly voiced announcer guy saying "In a universe where P==NP...", followed by 5 minutes of droning on about math. After that, it will cut to a female hacker with glasses reflecting complex equations from a bank of monitors, and it will finish up with some explosions and maybe a car flying through the air with Keanu Reeves in the driver's seat.
I've seen the film already - there have been a few screenings of it here in Cambridge, UK at the university maths department. (Indeed, I wasn't aware it hadn't been generally released!) It's an interesting idea and quite reasonably played out without too much cliche and, impressively, not too many blunders in maths or tech. The way the premise has been turned into plot is not, however, so sound. Still, I found it sufficiently engaging and I'd recommend a viewing for anyone with an academic maths or science background.
"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 use would exist within computer science. However, it's application would soon extend to countless other disciplines. For example, by utilizing the solution to P vs. NP, a hacker can 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."
So what is the P vs. NP problem?
Well, the P vs. NP problem is a real mathematics problem and is one of the seven Clay Mathematics Institute's Millennium Problems. A correct solution to any of the problems results in a $1,000,000 prize.
The Clay Institute states:
"Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. "
So what is the travelling salesman problem?
Well, the travelling salesman problem (TSP) is also a real mathematics problem and it asks the following question:
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. So you can see it is related the the P vs. NP problem!
In the book, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook, it states:
"Selecting the best tour through a set of points and knowing it is the best is the full challenge of the TSP. Users of a brute-force algorithm that sorts through all permutations can be certain they have met the challenge, but such an approach lacks both subtlety and, as we know, practical efficiency. What is needed is a means to guarantee the quality of a tour, short of inspecting each permutation individually. In this context, the tool...
Damn, and there I hoped it will be a trailer about a salesman in early 1900s (when the problem was starting to be defined and studied), traveling across Europe and trying to meet all the major European cities with the shortest amount of time, with overtones of disappearing the Victorian era and entering the new century with the ideals for new, more industrialized and exact world of 20th century with some foreshadowing into the rampant nationalism and two wars that followed. Was it the growing influence of math and algorithms (that made concepts like "Traveling Salesman problem" even possible) that directly or indirectly caused the genocides of the past century? All that could be asked by the salesman, traveling from city to city in the shortest amount of time, in the train, or maybe newly built Daimler-Mercedes car.
The website didn't load initially, so I allowed it javascript and cookies, fine. Then the hilarious "skip intro" button transported me back to the 90s. Then the website finally loaded with style over substance and a hilariously tiny window in which text appears. Thank god it loads up the whole website so you can at least disable the retarded CSS and view the text of the site - better than in most cases I guess.
I don't like where the web is going, it was on the right track with CSS but it's getting ridiculous again. Now I need javascript to read text and view pictures.
Interesting concept. Probably worthwhile as a teaching tool, but don't get your hopes up about it being good. The trailer doesn't impress, the 4.8 rating on IMDB is nothing to ignore, and I think wikipedia is being dishonest when it says "early reviews have been favorable" when in fact the two supporting citations both link to the same article that actually says this:
>Unfortunately, this means that the majority of the film consists of five men having a heated discussion in a stark, washed-out blue room in some anonymous government building. Other than Horton, we never even learn the characters’ names. The low-budget aesthetic and grounding in hard science is reminiscent of the excellent time-travel film Primer, but Travelling Salesman is far less ambitious. A few flashbacks help break up the film, but you can’t help think this particular story would be better served as an hour-long play.
And yea, it's clear that the film is at least partially inspired by Primer. I'm not sure if this really bothers me, though I once made a short film vaguely inspired by Primer and was harshly called out for it. Compare the trailers:
I'd wondered that too. Also wondered how transparent the glass would be: assuming the point would be rapid mass heating of the desert/beach in question a la nuclear weapon, the lack of material purity and uncontrolled heating would result in pretty poor glass, likely opaque. Trinitite isn't clear.
Even if P=NP, some problems still take a whole lotta work to solve, and "shortcuts" aren't much faster.
50 comments
[ 4.8 ms ] story [ 112 ms ] threadhttp://www.youtube.com/watch?v=6ybd5rbQ5rU
Well actually it reads
> Ratings: 4,8/10 from 53 users
so I do not think the population is big enough to be relevant.
GAs are not the best approach even for randomized heuristic approximations. Mostly they are cute, biologically intriguing programming exercises for people that don't care about sitting down and formally working out the specifications of a serious optimization problem. Often they end up throwing many CPU-hours at a relatively simple problem that they weren't even looking to solve, and get a sub-optimal solution because they didn't even bother to optimize the learning/mutation schedule, which would speed it up by an order of magnitude, but that would require maths and thinking, instead of just throwing more randomness against the wall because "it's evolution".
Genetic Algorithms aren't even easier to implement than other randomized heuristic approximations. For instance, Simulated Annealing is basically (but not quite) a GA with a population of one, so you don't need selection or crossover (do you use tournament selection or roulette selection? does it matter? will you try both? what will be your population size?). Simulated Annealing is much easier to implement and has fewer variables to optimize (such as the cooling/learning schedule). Of course it's not nearly as "sexy" as the biologically inspired genetic algorithm.
Most importantly however, a GA does not solve P?=NP, so it is not sufficient for the premise to this movie, which is about the consequences of solving P?=NP, not about arriving at suboptimal but perhaps sufficient solution in almost reasonable time to a TSP problem that doesn't actually have a practical use.
Also, AFAIK, a general solution to P=NP could still be very time consuming to calculate (even if you prove polynomial time solutions, that could still be a very high order polynomial). That is, your general solution to the problem could be only slightly better than O(n!) and satisfy.
I'm sure the underlying discussion of "What if P=NP? is solved?" is incredibly interesting but what I got from the trailer was that this was a movie with a bad script, bad cinematography, bad acting, and bad editing.
In some ways the trailer reminded me of Primer but it didn't quite make the low-budget vibe work in it's favor. Having made a few student films, but never having made a good short film, it's still hard for me to put my finger on the little differences that make something like this work.
So what is the movie about?
"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 use would exist within computer science. However, it's application would soon extend to countless other disciplines. For example, by utilizing the solution to P vs. NP, a hacker can 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."
So what is the P vs. NP problem?
Well, the P vs. NP problem is a real mathematics problem and is one of the seven Clay Mathematics Institute's Millennium Problems. A correct solution to any of the problems results in a $1,000,000 prize.
The Clay Institute states: "Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. "
So what is the travelling salesman problem?
Well, the travelling salesman problem (TSP) is also a real mathematics problem and it asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. So you can see it is related the the P vs. NP problem!
In the book, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook, it states: "Selecting the best tour through a set of points and knowing it is the best is the full challenge of the TSP. Users of a brute-force algorithm that sorts through all permutations can be certain they have met the challenge, but such an approach lacks both subtlety and, as we know, practical efficiency. What is needed is a means to guarantee the quality of a tour, short of inspecting each permutation individually. In this context, the tool...
http://www.youtube.com/watch?v=XkDHDYy_9cE
And instead I got guys sitting in a room. Damn.
I don't like where the web is going, it was on the right track with CSS but it's getting ridiculous again. Now I need javascript to read text and view pictures.
http://www.antipope.org/charlie/blog-static/fiction/toast/to...
Quick and worthy a read.
>Unfortunately, this means that the majority of the film consists of five men having a heated discussion in a stark, washed-out blue room in some anonymous government building. Other than Horton, we never even learn the characters’ names. The low-budget aesthetic and grounding in hard science is reminiscent of the excellent time-travel film Primer, but Travelling Salesman is far less ambitious. A few flashbacks help break up the film, but you can’t help think this particular story would be better served as an hour-long play.
And yea, it's clear that the film is at least partially inspired by Primer. I'm not sure if this really bothers me, though I once made a short film vaguely inspired by Primer and was harshly called out for it. Compare the trailers:
http://youtu.be/4CC60HJvZRE
http://youtu.be/6ybd5rbQ5rU
The trailer was quite reminiscent of Pi, right down to the [near] monochrome imagery and someone's head getting drilled.
Even if P=NP, some problems still take a whole lotta work to solve, and "shortcuts" aren't much faster.