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.'"
P=NP is now a buzzword, please add to bullshit bingo card.
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
Not sure if troll or just stupid...
I really want to know about Thriller in a world where P=NP. Do the zombies dance differently or what?
Not a horror film = no need for expendable minorities, I suppose.
An enigma, wrapped in a riddle, shrouded in bacon and cheese
"P. P never changes." in a Ron Perlman voice.
http://www.travellingsalesmanmovie.com/
Intelligence is largely controlled by early childhood educational opportunity, so it would be unsurprising if the 4 smartest were white.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
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
With the constant switches to a blue screen with the word 'simplified', I was primed for an IBM commercial close.
Cryptography relies on problems that are very hard to solve without a key, but when you have the key are easy. NP problems have the property that if you know the solution, it's easy to prove that you have the solution, but finding a solution is otherwise really hard. Take factoring for example, which is an NP problem - take two really big primes, and multiply them. Give the result away to anyone who asks. If the primes are big enough, they won't be able to figure out your original primes, but anyone who has either of the original primes can find the other with ease. RSA is dependant on that property. If I can find those two primes quickly from just public key, I've cracked RSA. If NP=P, then factoring is no longer a hard problem.
But P=NP will not help you crack anything.
IANAC but just what I remember from my CS degree, factorization is NP-complete, if it can be simplified to polynomial then maybe it's easier to crack something (public key systems that rely on the complexity of factorization like RSA) ? Shor's algorithm that works on a quantum computer does make it polynomial and it says in the link that it will have major implications to security schemes that rely on factorization (such as RSA).
I wonder if this movie is related to that (transforming sand to glass could be relevant to how Shor transformed the problem using the quantum Fourier transform)
I loved Pi!
http://www.imdb.com/title/tt0138704/
for those who missed it
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.
I often wonder why people invoke racism so often when it comes to these issues when the reality is... disadvantaged white kids often fare pretty poorly too. If one of your strongest indicators, do you really need race to explain why, generation after generation, racial dmeographics shift less than we "would like".
Yes the smartest in this society are probably mostly a bunch of white guys. Not because being white makes you better, or smarter, but because there are more white people who can give their children the opportunity to advance. Which isn't to say that being white people gave them that ability, but just that, the "initial condition" that we started with has done more to influence the outcome than we want to give it credit.
In short, I often feel racism is used as an excuse to deny the lack of real mobility within society....because if you don't think race/genetics is a major factor, then how do you explain the "lack of progress" along racial lines, if there is very high mobility? Seems to me it may be the lack of real mobility.
"I opened my eyes, and everything went dark again"
He probably made the mistake lots of people make, which is to think "NP hard" is similar to saying "rocket-science hard", where NP is just an adjective describing "hard". People don't realize that "NP-hard" is itself a formal class of problems that is not necessarily equivalent to NP. It's not his fault... its a horribly confusingly named set of concepts.
This really annoys me. You can't accept that they're white by chance? As in, they just happened to cast those actors? Having worked in the advertising industry (shudder) I can tell you how MADDENING it is when you've got a bunch of really good takes or photographs but you've got to discard them because you've been told by some bleeding heart retard that you need that one minority in there, who just so happens cannot pose in front of a camera to save their life. This leads to lots of post processing and other dicking around just to appease people like you, not to mention the subtle racism of including a single minority there in the first place. A great example: any number of car ads where the entire family is white and there's a token black boy in the backseat. Why yes that makes complete sense! Why not make the whole family black instead? Oh no, that would be *too many* minorities, they're called minorities for a reason afterall!
Which was pretty rad.
They're all male too - why didn't you pick up on that, you misogynist clod!
systemd is Roko's Basilisk.
I'm genuinely not sure how to exactly one's mind would have to work to even have noticed this without somebody else mentioning it to them (which in turn would raise the question of where the previous person heard it, and so on... where the causal chain ultimately reveals one sick-minded puppy).
Do you ordinarily go out of your way just to correlate any kind of entirely coincidental absence of a minority with the implication of deliberate racism, or is this just a one-time thing?
File under 'M' for 'Manic ranting'
Travelling and traveling are both valid spellings of the word, the former being more common in British English and the latter more common in American English.
It is pitch black. You are likely to be eaten by a grue.
Factorization is most likely not NP complete. Rather, it is in the intersection of NP and coNP, and it is widely believed that no NP complete problems are in coNP, for reasons similar to the reasons it is believed that no NP complete problems are in P. It is also unlikely that there is a "complete" class for the intersection of NP and coNP, which casts some doubt on the hardness of integer factorization.
Of course, if P=NP, integer factorization is definitely a theoretically feasible problem; this does not mean that it can be easily solved in practice, though. Maybe the best algorithm for integer factorization runs in O(n^100) time -- polynomial but still beyond the reach of any reasonable computer. P=NP would not imply that cryptography is impossible; rather, it would require some new definitions of security and entirely different approaches to cryptography.
Palm trees and 8
Your question is irrelevant since it didn't happen that way. The movie was filmed in a country that claims to be a melting pot and yet the "4 smartest ppl in the world" are a bunch of skinny white guys.
You're talking about an extremely small set. Let's reduce it further to just one: "The smartest person in the world". Now are you going to be upset if this person isn't representative of every culture?
Admittedly, this may be the result of my Western upbringing, but I think it might be accurate to portray the greatest living mathematicians as white -- with possibly an Indian or Asian or two. For the past few hundred years, most of the greatest mathematicians have been skinny white guys*. If you go back to the foundations of algebra, you do find some Persians (arguably "white") and some Indian guys. Given that the movie appears to be a US-centric one, it would have been pretty easy to throw in an Asian/Indian dude. Against my better judgment, I will go out on a limb and say that the African-American and Latino communities in the United States have not exactly produced a lot of notable mathematicians.
But I would agree that this looks like pretty lousy casting. Partly because most "white" guys in the US have shown declining math scores and partly because those dudes aren't nearly homely enough. Almost without exception, all the seriously capable math nerds I know have bad complexions, bad beards, and thick glasses. The trailer should also feature a scene where each of the smart guys is living at home with their mother.
* In the case of Kurt Gödel, very skinny.
In cryptography you're looking for a problem that is asymmetric. NP is your ideal, but as a lot of other people have pointed out, practical cryptographic algorithms are a not ideal. IBM actually had a cryptography algorithm based on the TSP once, but they must have found a flaw because it was never popularized.
A lot of people confuse NP and/or 'intractable' with 'impossible'. They do not mean the same thing. Intractable problems are often practically impossible, if for instance it would require more mass than the entire universe to calculate the answer. But since our understanding of physics is incomplete, we can't say for sure how big a 'perfect' computer you'd need to solve a certain problem, so you can't categorically say that it's impossible. All you can say is "we can't do it today." or "That's a problem for my grandchildren to deal with... hopefully."
Remember that for certain inputs an NP-Complete problem can be solved on the back of an envelope. If I tell you to place a dot in the middle of the envelope, and one more or less near each corner, you can find the shortest path in a few minutes. It's an NP complete problem, but it's still trivial to solve. NP is not a magic wall. It all depends on the context (ie, the inputs).
Just because it works, doesn't mean it isn't broken.
I often wonder why people invoke racism so often when it comes to these issues when the reality is... disadvantaged white kids often fare pretty poorly too. If one of your strongest indicators, do you really need race to explain why, generation after generation, racial dmeographics shift less than we "would like".
Yes the smartest in this society are probably mostly a bunch of white guys. Not because being white makes you better, or smarter, but because there are more white people who can give their children the opportunity to advance. Which isn't to say that being white people gave them that ability, but just that, the "initial condition" that we started with has done more to influence the outcome than we want to give it credit.
In short, I often feel racism is used as an excuse to deny the lack of real mobility within society....because if you don't think race/genetics is a major factor, then how do you explain the "lack of progress" along racial lines, if there is very high mobility? Seems to me it may be the lack of real mobility.
The lack of real mobility is a myth. I can say this because I come from a family that emigrated and came to the United States and started off on welfare, living in government projects, and going to very poorly supported schools. What made the difference for me were parents to valued education and pushed their kids to go beyond what was considered average. They convinced me, my siblings, and themselves, that the government handouts were temporary aids for us, and that continuing to live off the government when we have the ability to eventually make it on our own is shameful. My parents were farmers and made it as far as completing elementary school back in their homeland. So it isn't as if they had a great start, either. Yet my siblings and I, on the other hand, completed college, and I completed my Ph. D. in mathematics -- and we all went through public schools prior to college. If I were an exception, then we might call it "lack of mobility." The problem I see is that our government has made it too easy for those who have to rely on its social programs to do it for so long. For many, it is much easier to accept a very modest, but not-uncomfortable lifestyle of welfare and food stamps rather than to make an honest effort to move out of their current conditions.
Many immigrants who come to the US will have very similar stories of how they or their parents moved to the US with hopes of finding better opportunities. They often come from places where the conditions are so terrible that even the living in government projects and relying on the US welfare system is heavenly in comparison. Yet they do not fall into the welfare trap and eventually contribute to society like the rest of US citizens who were born and raised here. What they have that a lot of folks who are "stuck on welfare" is a drive. In my own parents' case, what drove them was their belief that if they could escape a communist government (that sought to execute anyone who defied it) by risking everything on a 2-piston boat set off into unknown waters, then they can certainly get out of welfare. This drive is lacking in a lot of families who are currently relying on government programs (I'm referring to families in which welfare reliance occurs for generations).
I didn't say there is no mobility, just that it is less than we would like. Even with very little mobility, you will always have edge cases.
Also, there are more issues than just being poor. If I were placing odds, I would give a person from a poor family with well educated parents much better odds than someone from a reasonably better family with uneducated (and I don't mean grade level completed so much as equivalency... I mean ability to read/write/do basic math maybe some algebra)
Of course, its also a matter of what you are taught and social attitudes. Did you know that the #1 predictor of a childs sucess in math is not, in fact, any of these factors but whether or not they believe that math is a skill that can be learned or a talent that is inborn.
Seriously.... just believing that you can learn it if you put the effort in is it. Which makes some amount of sense, if you don't believe you can learn it, then why would you waste your time studying it? Of course... where do we get attitudes like that? Do you think a kid is more or less likely to believe that he can learn math if the parents who raised him believed that it was an inborn talent?
"I opened my eyes, and everything went dark again"
Seriously, Stallman instead of Knuth?!
However it does not say "the world's four smartest mathematicians." It says "four of the world's smartest mathematicians."
The Tao of math: The numbers you can count are not the real numbers.
And we know that Asians aren't known for that or anything... Really, it wouldn't have been shocking to have a Japanese guy, or an Indian guy, or heck, maybe a woman.
The way the movie industry works, the cast would be three white guys and a blind black lesbian smarter than all of them.
Ezekiel 23:20
You forget that there is no way to decide in polynomial time if the text you got is the plaintext. That's why the one-time pad is provably secure: Every text of the same length could be the plaintext, and without knowing the key, you cannot distinguish between "Attack tomorrow 10:00" and "We should surrender!!"
The Tao of math: The numbers you can count are not the real numbers.
How long is this movie
O(n!)
For your next post, explain why anecdotal evidence is not used in scientific studies.
Due to circumstances beyond my control, I am master of my fate and captain of my soul.
Hardly - the United States is on par with petty dictatorships for income inequality and mobility. A young member of the working class can look forward to graduating with $25k or more in student loan debt and then struggling to find a job in a shitty economy while hoping they don't need health care. Whereas the rich don't have to worry about health care or student loan debt or housing and can afford to take a year long unpaid internship - or three - before getting a job.
I can say that's a logical fallacy. I know someone who won a lottery. Therefore, winning the lottery is a realistic expectation for the majority of the population.
Nice boilerplate pull-up-by-your-bootstraps talking points. And how about when they are six applicants for every open job? At least you have the self-awareness not to join the tea party.
I'd like to see Chris Rock as the fast-talking wacky crypto-dude who learned his math on the mean streets and back-alleys of L.A. Every time the plot lags, he busts out a wise crack.
And in my neck of the woods, travellling.