Forgot your password?
typodupeerror
It's funny.  Laugh. Math Movies Idle News

Travelling Salesman, Thriller Set In a World Where P=NP 165

Posted by Unknown Lamer
from the very-serious-faces-throughout dept.
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.'"

This discussion has been archived. No new comments can be posted.

Travelling Salesman, Thriller Set In a World Where P=NP

Comments Filter:
  • It is offcial (Score:2, Insightful)

    by M0j0_j0j0 (1250800)

    P=NP is now a buzzword, please add to bullshit bingo card.

  • In a world... (Score:5, Informative)

    by nitehawk214 (222219) on Wednesday April 25, 2012 @12:49PM (#39796555)

    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.

    • Your inner monologue is bad and you should feel bad!
    • by Chemisor (97276) on Wednesday April 25, 2012 @01:01PM (#39796743)

      "P. P never changes." in a Ron Perlman voice.

    • by Anonymous Coward on Wednesday April 25, 2012 @01:02PM (#39796755)

      I would've gone with "When everything you thought you knew about NP... is wrong"

    • by Culture20 (968837)
      I heard it in Bill Woodson's voice from Superfriends. "Meanwhile, in a world where P = NP..."
      • by Chris Burke (6130)

        Aquaman: "We'll never catch The Traveling Salesman! Not even the Bat Computer can match the efficiency of his route!"
        Superman: "Unless we can enhance the Bat Computer by using my Super Spinning to change the vibrations of space in the area..."
        Batman: "... to duplicate The Traveling Salesman's powers! It just might work!"

        Announcer: "Superman begins to spin faster than light, causing P to equal NP!"

        I'd watch that episode.

    • by shentino (1139071)

      May he rest in peace.

      September 1, 2008

    • The trailer is:

      "In a world where P = NP... cryptography becomes meaningless."

      Which of course is not true. The algorithm might still be O(n^100). While polynomial, this would still be practically intractable for moderately large n.

    • by SeaFox (739806)

      Sorry, I was still focusing on "Timothy LANZone! Now, there's an alpha-geek name!"

  • by Anonymous Coward

    I really want to know about Thriller in a world where P=NP. Do the zombies dance differently or what?

  • Cryptography? (Score:2, Informative)

    by Chemisor (97276)

    Since when is cryptography NP? Cracking any encrypted message takes a well-defined amount of time, derived from available computing power and the length and complexity of the key. Faster computers will help you here. Better factoring algorithms may help you here. But P=NP will not help you crack anything.

    • by alendit (1454311)

      NP can also take a well-defined amount of time, it is not the point of it. But you are absoluelly right, that factorisation algorithms do not have anything to do with P=NP, since the problem is not proven to be NP-complete.

      • Re:Cryptography? (Score:5, Informative)

        by adonoman (624929) on Wednesday April 25, 2012 @01:24PM (#39797113)
        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.
        • It means there should be, in theory, an algorithm that is substantially better than exponential explosion, which, in the case of long-number, almost-prime cryptography, means something substantially better than "try all possibilities", which is where we are now.

        • by alendit (1454311)

          This was not my understanding until now, but you are obviously correct. Thanks!

    • Re:Cryptography? (Score:5, Informative)

      by Surt (22457) on Wednesday April 25, 2012 @01:07PM (#39796839) Homepage Journal

      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.

      • by Anonymous Coward

        So much confusion here. You are correct that P=NP is theoretically relevant to factorising numbers because, as you point out, factorising numbers is somewhere between P and NP, so if P=NP then factorising is also P. The OP is correct first that complexity theory isn't terribly relevant to cryptography because considerations of worst case or even average case complexity say nothing about any specific key - you have no way to prove that the key you've got is actually worst-case. Complexity theory is never dir

    • by Ozan (176854)

      Cracking a key is NP hard, and with sufficiently large keys you can not amass enough computing power to crack them. If you can convert it to a P problem the computing time is reduced to practical dimensions. I think this film is about a sidestep ('melt the sand') that converts NP problems to P problems.

      • Cracking a key is NP hard

        No it isn't. It might not be in P, but it almost certainly is not NP hard. (Barring something like P=NP that would imply everything in P is NP hard)

        • 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.
      • Secret-Key cryptography - the traditional stuff like DES or AES, where you use the same key to encrypt and decrypt a message - typically doesn't use algorithms that would be affected by a constructive proof that P==NP. They're basically designed around complex messy mixing systems, not around hard math problems that would be simplified by a P=NP solution.

        Public-Key cryptography, of course, is all about hard math problems, though it turns out that NP-complete problems like knapsacks don't usually have the r

    • by hlavac (914630)
      You are talking about brute force, high bound on the work required to crack something. Any respectable encryption algorithm sets these reasonably high (like, use all computers on earth for thousands of years...). The problem is there may be shortcuts revealed thru cryptanalysis based on some properties of the cipher. And these are extremely valuable to certain people/agencies if they remain secret... these may involve such class of a problem. I can see a lot of material for a thriller plot there...
      • by Anonymous Coward

        It was called "Sneakers", and starred Robert Redford.

    • Re:Cryptography? (Score:4, Informative)

      by adonoman (624929) on Wednesday April 25, 2012 @01:19PM (#39797041)

      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 [wikipedia.org] 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

      • Re:Cryptography? (Score:5, Insightful)

        by betterunixthanunix (980855) on Wednesday April 25, 2012 @02:08PM (#39797715)
        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.
        • Secret-key crypto isn't dependent on NPish-hard problems, just on complex messiness, and it'll work fine even if we've got magic quantum computers. We'd have to go relearn all of those annoying Key Distribution System methods that public-key replaced, figure out what if anything to do about signatures, and have to build a whole lot of new business models for dealing with trust, since we'd have to actually trust the people running the KDC, but we'd live.

          • by CTachyon (412849)

            Secret-key crypto isn't dependent on NPish-hard problems, just on complex messiness, and it'll work fine even if we've got magic quantum computers. We'd have to go relearn all of those annoying Key Distribution System methods that public-key replaced, figure out what if anything to do about signatures, and have to build a whole lot of new business models for dealing with trust, since we'd have to actually trust the people running the KDC, but we'd live.

            This is not quite right. Secret key crypto will be fine if quantum computing becomes ubiquitous (or if we find out that P=BQP), but P=NP is a vastly more powerful result, to the extent that it would shatter secret key crypto as well. P=NP means that you can pluck answers to a question out of the aether with no more difficulty than checking if one random input answers the question. So if you know how to calculate "lambda key: ciphertext.decrypt(AES, key).matches(English)", then by P=NP magic you already k

    • Re:Cryptography? (Score:5, Informative)

      by Doubting Thomas (72381) on Wednesday April 25, 2012 @02:21PM (#39797925)

      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).

      • IBM actually had a cryptography algorithm based on the TSP once, but they must have found a flaw because it was never popularized

        There are cryptosystems based on [wikipedia.org] the knapsack problem, which is also NP-complete. (The basic idea is that your private key is a super-increasing set like 1,2,4,8... -- a special case for which the knapsack problem is easy -- but you disguise it via modular arithmetic as a plain ol' hard-as-fuck knapsack knapsack problem)

        But like with (what you say of) the IBM/TSP cryptosystem, they always seem to get broken -- not universally breakable, but commonly-breakable enough to fail crypto standards. I can't remem

  • Official Site (Score:5, Informative)

    by steamraven (2428480) on Wednesday April 25, 2012 @01:04PM (#39796785)
    http://www.travellingsalesmanmovie.com/ [travelling...nmovie.com]
  • by lpp (115405) on Wednesday April 25, 2012 @01:11PM (#39796897) Homepage Journal

    With the constant switches to a blue screen with the word 'simplified', I was primed for an IBM commercial close.

  • by Anonymous Coward

    But then I watched the trailer.

  • Is this the next Pi?

  • by Deliveranc3 (629997) <deliverance AT level4 DOT org> on Wednesday April 25, 2012 @01:40PM (#39797309) Journal
    Which was pretty rad.
    • by Anonymous Coward

      My voice is my passport. Verify me.

    • by Caspin (964414)
      "Hey, you guys wanna crash a few planes?"
    • by noahwh (1545231)

      Sneakers was a feature length film with a 35 million dollar budget and a cast of A-list actors.
      This is an 80 minute independent film starring the guy who played Submarine Captain Jim in Mega Piranha.

  • The P=NP aspect is just geekiness. You didn't solve it, and the movie had better not be about solving it. That would be stupid.

    You can, however, make a thriller using that as a MacGuffin. The better you know the math, the more rich-sounding the dialogue around the MacGuffin will be, but it must remain a MacGuffin. It's the Lost Ark from Raiders, or the Maltese Falcon. Either is a fine thriller, with interesting characters and snappy dialogue.

    You never want to read too much into a trailer, but I'm not seeing

  • Q: Does Danny Barclay's character make coffee?
    His character's name is Tim Horton.

  • Next thing you know they'll make a show about the Monty Hall problem. Oh wai-
  • Does the movie contain anyone ordering food in a restaurant like this [xkcd.com]?

"Life is a garment we continuously alter, but which never seems to fit." -- David McCord

Working...