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.'"

165 comments

  1. It is offcial by M0j0_j0j0 · · Score: 2, Insightful

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

    1. Re:It is offcial by Anonymous Coward · · Score: 2, Funny

      N = 1

      There you go. I solved it. Now where's my million bucks?!

    2. Re:It is offcial by Darinbob · · Score: 3, Insightful

      I'll hold off a bit on that. However once I hear hipsters using it in casual conversations at parties, or new age psychics explaining their abilities with it, then I'll know that P=NP is the new string theory.

    3. Re:It is offcial by maxwell+demon · · Score: 4, Funny

      That's not the complete solution. The complete solution reads: N=1 or P=0

      --
      The Tao of math: The numbers you can count are not the real numbers.
  2. Wasn't Numb3rs cancelled? by 1_brown_mouse · · Score: 0

    How long is this movie and will it have keen illuminating animated diagrams?

    1. Re:Wasn't Numb3rs cancelled? by Anonymous Coward · · Score: 1

      How long is this movie and will it have keen illuminating animated diagrams?

      Unless that word is being preceded by "Commander", do not use it.

    2. Re:Wasn't Numb3rs cancelled? by Anonymous Coward · · Score: 1

      Nonsense. Keen is a perfectly valid prefix for slicing or piercing weapons, although a little superfluous if you have the improved critical faet for that weapon type.

    3. Re:Wasn't Numb3rs cancelled? by MisterZimbu · · Score: 5, Funny

      How long is this movie

      O(n!)

    4. Re:Wasn't Numb3rs cancelled? by Half-pint+HAL · · Score: 1

      Because, of course, vocal outpourings of grief are frowned upon in modern society.

      --
      Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
  3. In a world... by nitehawk214 · · Score: 5, Informative

    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
    1. Re:In a world... by kaellinn18 · · Score: 1

      Your inner monologue is bad and you should feel bad!

      --

      --------
      This isn't the sig you're looking for. Move along.
    2. Re:In a world... by Anonymous Coward · · Score: 5, Funny

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

    3. Re:In a world... by Zsub · · Score: 0

      Oh dear, I'm terribly sorry but I misclicked. Now I have to comment =/

    4. Re:In a world... by Anonymous Coward · · Score: 0

      Because of the day when cryptography becomes meaningless, I'm staying away from P2P encrypted backup services.

    5. Re:In a world... by Culture20 · · Score: 1

      I heard it in Bill Woodson's voice from Superfriends. "Meanwhile, in a world where P = NP..."

    6. Re:In a world... by shentino · · Score: 1

      May he rest in peace.

      September 1, 2008

    7. Re:In a world... by maxwell+demon · · Score: 2

      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.

      --
      The Tao of math: The numbers you can count are not the real numbers.
    8. Re:In a world... by Chris+Burke · · Score: 1

      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.

      --

      The enemies of Democracy are
    9. Re:In a world... by Anonymous Coward · · Score: 0

      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.

      Guess I'm bad then, cause I heard it in Pablo Francisco's voice.

    10. Re:In a world... by SeaFox · · Score: 1

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

    11. Re:In a world... by Anonymous Coward · · Score: 0

      It's sad because P=NP is probably one of the infinitely many statements that is true but unprovable, though we obviously haven't been able to prove *that* either. So I doubt it will ever be the downfall of our society, unless it eventually drives all of our mathematicians crazy trying to prove something that cannot actually be proven.

      Sometimes I wonder if we could attack it by figuring out the minimum number of bits of information necessary to solve a problem and comparing that to the problem size, but I suspect that "minimum number of bits of information necessary to solve a problem" is not a computable function, that it varies with the method used (e.g. sorting via comparison is n lg n, but there are non-comparison sorts), and that we have no way to iterate over all solution methods.

    12. Re:In a world... by garyebickford · · Score: 1

      Dang, I had written up a nice answer and then accidentally surfed to another page.

      See Complexity - it's quite interesting. IIRC, the question of "the minimum number of bits to solve a problem" is itself in NP.

      Whether it is in Goedel's class of things that are true but unprovable, hmmm. Could happen. Certainly has happened, empirically, so far. :)

      --
      It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
    13. Re:In a world... by QQBoss · · Score: 2

      "Surfed to another page" is the new "but I didn't have enough space in the margin".

  4. Re:Maybe they should solve by alendit · · Score: 4, Funny

    Not sure if troll or just stupid...

  5. What's Michael Jackson's role? by Anonymous Coward · · Score: 2, Funny

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

    1. Re:What's Michael Jackson's role? by isj · · Score: 1

      Not exactly a thriller, but I enjoyed Charles Stross' Antibodies

  6. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Would it still be racist if the movie was filmed in Japan and everyone in the movie was Japanese?

  7. Robert Downey, Sr. by Anonymous Coward · · Score: 0

    I heard Robert Downey (Sr.) from Boogie Bights.

    Is that like YP !=MP?

    You, Your Problem isn't My Problem?

    What, no Boogie Nights fans here?

  8. Here you go. by Dr.+Manhattan · · Score: 1
    --
    PHEM - party like it's 1997-2003!
  9. In a world where movie trailers rock... by Anonymous Coward · · Score: 0

    ...how do they manage to make one so boring?

  10. Re:How come everyone in the movie is white? by CanHasDIY · · Score: 2

    Not a horror film = no need for expendable minorities, I suppose.

    --
    An enigma, wrapped in a riddle, shrouded in bacon and cheese
  11. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    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.

  12. Cryptography? by Chemisor · · Score: 1, Informative

    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.

    1. Re:Cryptography? by Anonymous Coward · · Score: 0

      If there was a miracle algorithm, you could use it to prove the feasibility of cracking the cryptography.

    2. Re:Cryptography? by alendit · · Score: 0

      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.

    3. Re:Cryptography? by Surt · · Score: 5, Informative

      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
    4. Re:Cryptography? by Ozan · · Score: 1

      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.

    5. Re:Cryptography? by hlavac · · Score: 1

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

    6. Re:Cryptography? by Captain+Segfault · · Score: 1

      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)

    7. Re:Cryptography? by adonoman · · Score: 3, Informative

      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.

    8. Re:Cryptography? by dominious · · Score: 2

      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)

    9. Re:Cryptography? by adonoman · · Score: 5, Informative

      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.

    10. Re:Cryptography? by WeirdAlchemy · · Score: 2

      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.

    11. Re:Cryptography? by Anonymous Coward · · Score: 0

      Sigh, if you own a CS degree, just burn it please.

    12. Re:Cryptography? by Impy+the+Impiuos+Imp · · Score: 1

      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.

      --
      (-1: Post disagrees with my already-settled worldview) is not a valid mod option.
    13. Re:Cryptography? by Anonymous Coward · · Score: 0

      Since when is cryptography NP?

      Not allt Crypto is in NP, but RSA is.

      Cracking any encrypted message takes a well-defined amount of time, derived from available computing power and the length and complexity of the key.

      Not exactly. just take a look at the wep encryption. it started as infeasible, then dangerous, and now it is basically cleartext, but we haven't advanced *that* much in computing power. They found bugs in the algorithm.
      In different ways, cryptography experts try to find bugs in the algorithms. This may means bugs in the underlying math.
      Now, lots of encryption algorithms make assumptions, such as "factorization of big numbers is really difficoult", but if we prove that factorization is actually really simple, the whole algorithms fall apart. That's why P=NP would kill RSA (but not others).

      Faster computers will help you here. Better factoring algorithms may help you here. But P=NP will not help you crack anything.

      Do you actually know anything about cryptography?
      If P=NP then it means we can factorize any number almost instantly. There are a lot of ways to reconduct a problem to an other one.
      once we find ONE problem NP-HARD and can reconduct it to P, *all other* NP-HARD problems can be automatically be found to have a corresponding problem in P.
      You just miss a lot of knowledge in complexity theory.

    14. Re:Cryptography? by Anonymous Coward · · Score: 1

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

    15. Re:Cryptography? by alendit · · Score: 1

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

    16. Re:Cryptography? by betterunixthanunix · · Score: 5, Insightful

      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
    17. Re:Cryptography? by Anonymous Coward · · Score: 0

      NP: Nondeterministic Polynomial => if I can guess right, I can prove my guess correct in polynomial time.

      Encryption: plaintext + key* => cyphertext
      Decryption: cyphertext + key* => plaintext
      Cryptanalysis: cyphertext + ? => plaintext

      Any useful decryption algorithm must finish in a reasonable amount of time when I have the key, so cryptanalysis cannot be harder than NP (once we're past unicity distance), so if P = NP there must be an algorithm that can decrypt the cyphertext without the key in polynomial time. Granted, polynomial time doesn't necessarily mean a short time, but it puts things on much more of the same playing field than when you get to mutliply the attacker's work while merely adding to the defender's simply by adding bits to the key.

      *The two keys will be the same in a symetric algorithm, and different-but-related in an assymetric algorithm, but that's not actually relevant here.

    18. Re:Cryptography? by Doubting+Thomas · · Score: 4, Informative

      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.
    19. Re:Cryptography? by Anonymous Coward · · Score: 1

      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 directly relevant to a specific computation anyway, because it concerns what happens as the input size approaches infinity, which is not something that can happen on finite computers.

      The basic premise of the movie is correct in that if someone comes up with a practically useful algorithm that proves that P=NP, then that could have far reaching consequences. Proving that P=NP is really just an irrelevant theoretical detail for those consequences, because the consequences would be exactly the same if someone came up with an algorithm that could solve any practical size NP problem in a short amount of cycles, even if that algorithm was theoretically not polynomial time.

    20. Re:Cryptography? by gv250 · · Score: 1

      (Barring something like P=NP that would imply everything in P is NP hard)

      That would be cool. I know, let's make a movie about the consequences of P=NP!

    21. Re:Cryptography? by maxwell+demon · · Score: 4, Informative

      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.
    22. Re:Cryptography? by Anonymous Coward · · Score: 0

      So much confusion here

      Isn't it ironic..

      factorising numbers is somewhere between P and NP

      The decision problem for integer factorization is in NP (and possibly also in P), not "somewhere between P and NP", which doesn't even exist. P is a (proper?) subset of NP.

    23. Re:Cryptography? by Anonymous Coward · · Score: 0

      One of the earliest asymmetric cryptography algorithms was the Merkle-Hellman cryptosystem, relying on the widely-known NP-complete subset sum problem.

    24. Re:Cryptography? by Anonymous Coward · · Score: 0

      (once we're past unicity distance)

    25. Re:Cryptography? by Anonymous Coward · · Score: 0

      Decision TSP is NP-Complete, all NP-Complete problems are inter-reductible in polynomial time(one algorithm for one can be modified to solve another).
      The prime factorization decision problem(relevant for cryptography) is co-NP and NP, it is unknown if it is NP-Complete.
      If someone solved TSP in P it then all NP are also P, including factorization but, if I'm not in error, we would still need to find the algorithm.

      Still the effects would be far more interesting for either direction of a proof in the case of NP-Hard problems(please remember or learn that not all NP-Hard are in NP, they're just at least as "hard" as any NP-Complete but can be "harder").

    26. Re:Cryptography? by Anonymous Coward · · Score: 0

      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.

      Not necessarily. Just because there is a solution in P doesn't mean you can crack encryption faster. There could be a polynomial solution whose constant is a zillion times the time that it takes to try all solutions for all currently used encryption. So, if your key was a zillion bits long, it might be faster than trying all the keys, but for say a 512 bit key, it could be 100000000000 times longer than trying all possible keys or something.

       

    27. Re:Cryptography? by Surt · · Score: 1

      Absolutely true, though I've yet to see an example of this turn up in reality (and that might reflect some other unknown law of mathematics).

      --
      "Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
    28. Re:Cryptography? by DriedClexler · · Score: 1

      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 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 remember the reason why they keep failing though.

      --
      Information theory is life. The rest is just the KL divergence.
    29. Re:Cryptography? by Anonymous Coward · · Score: 0

      That depends. If all you have is the ciphertext, and no part of the key, then you're correct that you can't prove which possible plaintext is correct, barring heuristic methods. For a public key system, however, it's trivial to determine if you've found the plaintext: simply re-encrypt it and see if it matches the ciphertext. Any practical encryption method will be in P.

      Generally, when we discuss attacks on public key systems, we assume we have the public part of the key, because we're trying to attack the mathematical problem that makes it hard to compute the private part from the public one. For private key systems, or public key systems where we don't have any part of the key, P=NP doesn't help much at all.

    30. Re:Cryptography? by Alsee · · Score: 1

      You forget that there is no way to decide in polynomial time if the text you got is the plaintext.

      Actually there is a way to tackle that issue. A plaintext is typically highly compressible, while a failed decryption is effectively random. There is there is a statistically zero probability for any failed decryption to be as compressible as the true text. So you reformulate the problem as "What password returns the shortest length when decryption AND compression are applied". If by sheer fluke you do get a junk password yielding a garbage result, you can simply try again asking for the password that returns the second-most-compressible result.

      This technique yields the interesting result that you want to apply an optimal compression algorithm to your files before encrypting them. That way you are encrypting effectively random data, so that an attacker cannot use this sort of method to identify a successful decryption.

      At that point it depends upon whether the attacker knows (or can guess) any other information that can be used to identify a successful decryption. For example if he knows the file type, or keywords that you are likely to appear in the text, that can be used to automatically identify or massively narrow down potentially correct decryptions. If it is text you wrote, then an attacker could use a sample of your other writing to match against the statistics of your personal writing style. People have already demonstrated programs that can match multiple texts from the same author with significant reliability. The attacker would probably have to sort through a number of false-positive password candidates, but if the attacker knows (or can guess) anything significant about the encrypted data there is a good chance he can decrypt it.

      -

      --
      - - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
    31. Re:Cryptography? by Anonymous Coward · · Score: 0

      This technique yields the interesting result that you want to apply an optimal compression algorithm to your files before encrypting them. That way you are encrypting effectively random data, so that an attacker cannot use this sort of method to identify a successful decryption.

      Except applying the corresponding decompression after decryption, of course.

      At that point it depends upon whether the attacker knows (or can guess) any other information that can be used to identify a successful decryption. For example if he knows the file type, or keywords that you are likely to appear in the text, that can be used to automatically identify or massively narrow down potentially correct decryptions. If it is text you wrote, then an attacker could use a sample of your other writing to match against the statistics of your personal writing style. People have already demonstrated programs that can match multiple texts from the same author with significant reliability. The attacker would probably have to sort through a number of false-positive password candidates, but if the attacker knows (or can guess) anything significant about the encrypted data there is a good chance he can decrypt it.

      This helps to make the difference between garbage and meaningful text. Still doesn't help at all to tell if the message was "Attack tomorrow 10:00" or "We should surrender!", which are both meaningful sentences.

      Look: generating all possible outputs from a one-time pad encrypted message of length n equals generating all possible strings of length n. You can do that even without the ciphertext, so what you are doing is basically trying to guess the message without any input. Ok?

    32. Re:Cryptography? by Anonymous Coward · · Score: 0

      NFS and QS are much faster than complete trial and error, educate yourself before pontificating.

    33. Re:Cryptography? by Anonymous Coward · · Score: 0

      There is there is a statistically zero probability for any failed decryption to be as compressible as the true text.

      This is quite incorrect for a system with perfect secrecy, such as the one time pad the GP was talking about, or a cryptogram shorter than the unicity distance of the cipher. There is no way to determine if a particular solution is correct because every possible solution is equally as likely as any other. Please see Shannon's Communications Theory of Secrecy Systems for more information.

    34. Re:Cryptography? by Alsee · · Score: 1

      This technique yields the interesting result that you want to apply an optimal compression algorithm to your files before encrypting them. That way you are encrypting effectively random data, so that an attacker cannot use this sort of method to identify a successful decryption.

      Except applying the corresponding decompression after decryption, of course.

      You don't have the decryption yet. You need an algorithm to obtain a potential decryption. If P=NP then you can use an algorithm to (relatively quickly) find and give you the most compressible decryption. And the most compressible decryption is almost certainly the correct decryption. If the message is already compressed then you need some other way for an algorithm to pick out what potential decryption to give to you. For example if you know a specific name probably appears in the true text then you could try using an algorithm that returns decompressed potential decryptions that contain a specific name. You need to know or guess something about the text in order to write an algorithm which returns the correct decryption.

      Still doesn't help at all to tell if the message was "Attack tomorrow 10:00" or "We should surrender!", which are both meaningful sentences.

      If the message length is so short that it is comparable in length to the key, then yeah, you'd get a huge number of "meaningful sentence" possible decryptions with no way to pick the right one. However for any message significantly longer than the key, the probability of rapidly approaches zero that there would exist more than one meaningful proper-English decryption.

      Look: generating all possible outputs from a one-time pad encrypted message

      I obviously was not talking about one-time pads. The comments I was responding to were not about one time pads.

      -

      --
      - - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
  13. Re:How come everyone in the movie is white? by darthdavid · · Score: 1

    Your point is correct but you've chosen a pretty hilariously ironic example to use given the deeply rooted racist tendencies of Japanese society...

  14. Better yet... by Chemisor · · Score: 4, Funny

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

    1. Re:Better yet... by Anonymous Coward · · Score: 0

      hahahahahahaha

    2. Re:Better yet... by Anonymous Coward · · Score: 0

      How about in Grigori Perelman's voice instead?

  15. Official Site by steamraven · · Score: 5, Informative
  16. Re:How come everyone in the movie is white? by Surt · · Score: 5, Interesting

    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
  17. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    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.

  18. IBM by lpp · · Score: 2

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

  19. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Don't bother, their neckbeards repel any questioning of their privilege in society.

  20. I was excited when I read the ./ article by Anonymous Coward · · Score: 1

    But then I watched the trailer.

  21. Is this the next Pi?

    1. Re:Pi by fragfoo · · Score: 1

      No, only if it was titled Tau.

      --
      Sig? Heil
  22. Goose bumps, again? by G3ckoG33k · · Score: 4, Interesting

    I loved Pi!

    http://www.imdb.com/title/tt0138704/

    for those who missed it

    1. Re:Goose bumps, again? by Anonymous Coward · · Score: 1

      Pi was good, but more trippy than mathy. I preferred Primer.

      In the "What if P=NP" genre, try the short story "Antibodies" by Charles Stross.

    2. Re:Goose bumps, again? by Mass+Overkiller · · Score: 0

      +1 for Primer!

  23. Re:How come everyone in the movie is white? by TheCarp · · Score: 4, Insightful

    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"
  24. Re:How come everyone in the movie is white? by NoSleepDemon · · Score: 2, Interesting

    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!

  25. It's like a sequel to Sneakers by Deliveranc3 · · Score: 5, Insightful

    Which was pretty rad.

    1. Re:It's like a sequel to Sneakers by Anonymous Coward · · Score: 1

      My voice is my passport. Verify me.

    2. Re:It's like a sequel to Sneakers by Caspin · · Score: 1

      "Hey, you guys wanna crash a few planes?"

    3. Re:It's like a sequel to Sneakers by noahwh · · Score: 1

      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.

    4. Re:It's like a sequel to Sneakers by Anonymous Coward · · Score: 0

      I want peace on Earth and goodwill towards Man.

    5. Re:It's like a sequel to Sneakers by Anonymous Coward · · Score: 0

      Sneakers II: The Sneaquel

    6. Re:It's like a sequel to Sneakers by tehcyder · · Score: 1

      Sneaks on a plane.

      --
      To have a right to do a thing is not at all the same as to be right in doing it
    7. Re:It's like a sequel to Sneakers by gurumeditationerror · · Score: 1

      "We are the CIA, we don't do that kind of thing!"

  26. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    This is a Euro/American-centric view.

    There are billions of Asians of all regions (India, China, Japan, Korea, etc.) and they have exceptional talent as well.

    Your own personal experience and privilege are blinding you to the truth that the media we consume is subject to the very same biases you contain in yourself. It becomes self-validating. You're in an echo chamber of people claiming the same tripe you are spouting here.

  27. Re:How come everyone in the movie is white? by wonkey_monkey · · Score: 2

    They're all male too - why didn't you pick up on that, you misogynist clod!

    --
    systemd is Roko's Basilisk.
  28. Re:How come everyone in the movie is white? by mark-t · · Score: 2

    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?

  29. Re:Maybe they should solve by khellendros1984 · · Score: 2

    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.
  30. The Mine Sweeper. by Anonymous Coward · · Score: 0

    Reminds me of the mine sweeper movie.

  31. Re:How come everyone in the movie is white? by Culture20 · · Score: 3, Interesting

    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?

  32. Re:How come everyone in the movie is white? by sneakyimp · · Score: 2

    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.

  33. Well, that looks pretty awful by jfengel · · Score: 1, Interesting

    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 much of either of those here. It put way too much on its surface: the blue wash to look cold, the deep dissonant chords on the piano, the "oh my god this is the end of the world" dialogue. I got no sense that I might care about the characters, or that they might do anything interesting or distinctive.

    Geeks love a movie where their geekiness gets tickled. Everybody loves a movie about themselves, and getting that aspect right makes the characters feel more real. I'm a geek. But I'm also more than a geek. I'd rather not be patronized, and the one thing I know for certain is that you didn't actually do anything about P=NP. Use it as background for solid performances, deep characterizations, and interesting visual composition, not instead of it.

    Maybe I'm wrong. Trailers are often not representative of the movie, and maybe there's good, non-trite dialogue in the rest of it. But I'm not hopeful.

  34. Re:How come everyone in the movie is white? by jimbolauski · · Score: 1, Funny

    Would it still be racist if the movie was filmed in Japan and everyone in the movie was Japanese?

    All Japanese movies are required by law to have Godzilla in them and thus everyone would not be Japanese.

    --
    Knowledge = Power
    P= W/t
    t=Money
    Money = Work/Knowledge so the less you know the more you make
  35. Spelling by Anonymous Coward · · Score: 0

    It probably would have been better to spell "traveling" correctly.

    1. Re:Spelling by maxwell+demon · · Score: 1
      --
      The Tao of math: The numbers you can count are not the real numbers.
  36. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Eliezer Yudkowsky is smarter than the other three. He said so himself.

  37. Re:How come everyone in the movie is white? by TheCarp · · Score: 1

    I think you are the one missing the point. The context of the discussion was about character placement in a film thats supposed to take place HERE. What goes on in other places doesn't matter in this context, in fact, its explicitly irrelevant.

    --
    "I opened my eyes, and everything went dark again"
  38. Obligatory... by Anonymous Coward · · Score: 0

    Male character, mid 50s, mustache, pointing at a security camera, screaming... "Consequences will never be the same!!!"
    It should've been in the trailer.

  39. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    You have either been misinformed or you just made that up. Your statement only makes sense if you are talking about some measurable kind of intelligence, in which case you are talking about IQ (it is nearly impossible to devise a test of mental skills that does not also measure IQ). There is a large hereditary component to IQ as extensively documented by twins-reared-apart studies. There is also a significant impact of environment, but the way in which the environment impacts IQ is not known, except for avoiding overtly harmful things like if you lock the child in a closet for a few years or provide completely insufficient nutrition.

    What is known is that IQ is not much impacted by any of the things that would seem obvious, like education, access to books, supportive parents or stimulating childhood environment. Smart people tend to have those things in their upbringing because their parents are also smart, so they are more likely to have the money and the desire to provide those things, but it is not a causal relationship. There is a significant impact of environment, but it is most certainly not largely down to early childhood educational opportunity as documented by intervention studies.

    If there was a known sure-fire way to increase people's intelligence (in the sense of IQ) from a simpleton to genius-level, don't you think everyone would know about it and immediately make sure to provide that for their children? We would all be geniuses if that were the case, or at least everyone who grew up with good access to education should then be a genius as an adult. The world I'm living in certainly does not support that hypothesis.

  40. Re:How come everyone in the movie is white? by rs1n · · Score: 5, Insightful

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

  41. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Intelligence is largely controlled by early childhood educational opportunity...

    When I was a kid, I recall the pointless gifted and talented programs and the nightmare that was the private school people tried sending me to. I refused to sit in alphabetical order during lunch and their other fun socipathic activities, and no doubt proved to everyone I was an idiot.

    Telling people their whole life is determined by the first couple years is a lie. It has nothing to do with what's best for the kid or increasing their intelligence. It robs the kid of having a genuine reason of their own to care about learning. Just an extension of the mindless, but capable factory worker that regular schools produce. So, I probably would've been an academic drone instead, or whatever they decided to tell me to be.

  42. Re:Maybe they should solve by ArhcAngel · · Score: 1

    Which is little comfort for Dan Quayle

    --
    "A person is smart. People are dumb, panicky dangerous animals and you know it." - K
  43. Q: Does Danny Barclay's character make coffee? by denis-The-menace · · Score: 1

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

    --
    Obama's legacy: (N)othing (S)ecure (A)nywhere and (T)error (S)imulation (A)dministration
  44. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    an intellectual thriller about four of the world's smartest mathematicians

    You are the one missing it.

    The movie is targeting its audience by casting how it did, it isn't trying to reflect the reality of our planet and its talent. You are trying to argue that it is representative of reality when it is actually in the media echo chamber that you live your life in.

    It is explicitly relevant because it says "world". And because of your own biases (not a bad thing) you don't realize that the media you consume is presenting a distortion of reality.

  45. Re:How come everyone in the movie is white? by TheCarp · · Score: 2

    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"
  46. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Woman? LOL

  47. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Oh, oh, I know this one! It's because they don't anticipate releasing the movie in many Samoan movie theaters (for example).

  48. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 3, Insightful

    Seriously, Stallman instead of Knuth?!

  49. Re:How come everyone in the movie is white? by ad0gg · · Score: 1

    I disagree with this statement. Intelligence is mostly controlled by your genes, it isn't even disputed in the science community. Has nothing to do with how you were raised. There's a bunch of studies on adopted kids and twins that were raised apart. No one ever likes to talk it about because for certain reasons i won't bring up because this type science has been used to commit some of worst crimes against humanity in modern history. Also IQ doesn't mean successful, being successful has to do with your upbringing and education. Smartest guy in the US is a bouncer after dropping out of college. He grew up in poverty and a broken home.

    The 2006 edition of Assessing adolescent and adult intelligence by Alan S. Kaufman and Elizabeth O. Lichtenberger reports correlations of 0.86 for identical twins raised together compared to 0.76 for those raised apart and 0.47 for siblings.[42]

    --

    Have you ever been to a turkish prison?

  50. Re:How come everyone in the movie is white? by maxwell+demon · · Score: 4, Informative

    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.
  51. Re:How come everyone in the movie is white? by K.+S.+Kyosuke · · Score: 4, Funny

    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
  52. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    She'd also have to have some magic or spiritual thing going on.

  53. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Why is this modded flamebait? I've been in similar situations-- had to use the shittiest monologue video (some talking head thing for an auto spot) because it fit the profile/specs.

    However, I think if you're in the ad industry it's called "fitting the demographic" and not "appeasing.... the bleeding heart retard(s)".

  54. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Care to make a wager?

  55. Re:How come everyone in the movie is white? by Surt · · Score: 1

    I don't know what studies you're reading. The ones I've read reach nearly the opposite conclusion. So at best we could chalk this up to 'science in the field is unclear'.

    --
    "Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
  56. Re:How come everyone in the movie is white? by dkleinsc · · Score: 1

    It would be a big mistake to assume that the opportunities available for Cuban-American immigrants in Miami (which is what I'm guessing you are based on your post) are identical to the opportunities available for African-Americans in the worst neighborhoods in Detroit. I'm not saying drive doesn't count, but in order to succeed a person needs both drive and opportunity. Someone with no opportunities can't succeed no matter how much they're driven to do so.

    You made the most of what you could do, and you have every right to be proud of it. But that doesn't mean everybody could have done what you did with the same talent and drive.

    --
    I am officially gone from /. Long live http://www.soylentnews.com/
  57. Next thing you know by Kuukai · · Score: 1

    Next thing you know they'll make a show about the Monty Hall problem. Oh wai-

    --
    Sendou Wave Kick!!
  58. Re:How come everyone in the movie is white? by regular_gonzalez · · Score: 2

    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.
  59. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    For your next post, explain why slashdot arguments do not count as scientific studies.

  60. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    yeah yeah, you're from the the greatest family of special snowflakes ever.
    get over yourself, dude.
    look around.
    yes, your story is exceptional. There are reasons for that beyond "everyone else is a lazy bastard".

  61. Re:How come everyone in the movie is white? by Uberbah · · Score: 2, Insightful

    The lack of real mobility is a myth.

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

    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.

    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.

    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.

  62. Re:How come everyone in the movie is white? by drkim · · Score: 2

    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.

  63. 1:23 by Anonymous Coward · · Score: 0

    is why this will be a great movie.

    1. Re:1:23 by Anonymous Coward · · Score: 0

      http://downloads.securityfocus.com/vulnerabilities/exploits/ie_xp_pfv_metafile.pm

  64. To be honest... by Sketchly · · Score: 1

    ... it sounds boring as fuck. Are there any car chases, explosions or scantily-clad fembots? I somehow doubt it.

  65. Re:How come everyone in the movie is white? by ScentCone · · Score: 1

    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?

    There are people for whom that is profession - folks who make six figures noticing that, spinning up faux outrage, and holding people hostage for cash over it. Don't be surprised that it's also some other people's hobby, and the lens through which they look at everything.

    --
    Don't disappoint your bird dog. Go to the range.
  66. Re:How come everyone in the movie is white? by Anonymous Coward · · Score: 0

    Someone has to get the sandwiches...

  67. Re:How come everyone in the movie is white? by bcrowell · · Score: 1

    I also don't know what studies you're reading. The ones I've read reach nearly the opposite conclusion. So at best we could chalk this up to 'science in the field is unclear'.

    Nor do I know where the AC was getting his info, but he's right and you're wrong. IQ is highly heritable. WP has a detailed article on this. Reference 7 in the WP article is to a 2004 meta-analysis that puts the heritability figure at about 85% (meaning that heredity explains about 85% of the variance in adult IQ).

    I also don't see what this has to do with the movie. There is a very simple explanation for the fact that, for example, most Nobel prize winners are white. It's because access to education is highly correlated with being white. You don't have to invoke any hypothetical cause and effect relationship between early childhood education and intelligence. There are just a lot of dark-skinned kids in places like Brazil and Tanzania who have zero chance of becoming professional scientists.

  68. Nonsense - probably disprovable or maybe provable by billstewart · · Score: 1

    It's highly likely that somebody will eventually be able to prove it to be true or false. (The current thinking is that it's probably false, given the number of smart people who've been looking for it, but we could be surprised.) This isn't one of those "Gödel says this statement isn't a lie" sorts of problems, nor is it likely to be a "Proof won't fit in a single human brain" problem. And unless Charlie Stross is right, it's not even one of those "Maths that are too dangerous for mere mortals to meddle with" problems that evoke elder beings from other dimensions that #@#@!#~~~~~~~~

    --

    Bill Stewart
    New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
  69. Public-Key vs. Secret-Key Crypto and P?=NP by billstewart · · Score: 1

    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 right structure to build successful crypto, and we've ended up with problems that are based on factoring instead, which might turn out to be easier than the NP-complete problems (or if P=NP is true, it's possible that factoring could actually be harder.)

    A mathematical solution to P==NP or factoring or a sufficiently useful quantum computer could trash public-key cryptography (either break it entirely, or at least weaken it enough that you need keys that are impractically long), but that wouldn''t trash secret-key computing. For instance, Shor's quantum factoring algorithm at most forces you to double the key length for symmetric-key crypto.

    So it would be really annoying, and would force us to use the kinds of key distribution systems we had before public-key. Typically they involve a Key Distribution Center with per-user secret keys that have to be heavily protected and let you request session keys that are transmitted to the sender and recipient of a communication, so the whole system is vulnerable if the KDC is compromised, and is vulnerable to traffic analysis if you're not very careful - but you could do it.

    --

    Bill Stewart
    New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
    1. Re:Public-Key vs. Secret-Key Crypto and P?=NP by Anonymous Coward · · Score: 0

      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.

      Pick any cryptosystem (symmetric or asymmetric, except one-time pad of course). If you have a key, is it "easy" (=possible within polynomial time) to check if the key will decrypt a cipher text? Well, almost certainly, otherwise it would be a pretty impractical cryptosystem. This means that the problem (including a "complex messy mixing system" ) is in NP. If P = NP, it means that _any_ problem in NP can be solved in polynomial time. Of course, a non-constructive proof of P=NP would not directly break any cryptosystem, and even a constructive proof would still require one to come up with an algorithm to transform the crypto-problem to one that can be solved by the constructive proof.

      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 right structure to build successful crypto, and we've ended up with problems that are based on factoring instead, which might turn out to be easier than the NP-complete problems (or if P=NP is true, it's possible that factoring could actually be harder.)

      NPC-problems are polynomial time reducible to any other problem in NP. Factoring is in NP. Therefore factoring cannot be harder than any NPC-problem.

    2. Re:Public-Key vs. Secret-Key Crypto and P?=NP by Lokitoth · · Score: 1

      Pick any cryptosystem (symmetric or asymmetric, except one-time pad of course). If you have a key, is it "easy" (=possible within polynomial time) to check if the key will decrypt a cipher text? Well, almost certainly, otherwise it would be a pretty impractical cryptosystem.

      Disagree. It is possible to construct a CryptoFunction C(t, k) such that exists k_0 != k where D(t, k_0) = t_0 != t, with t_0 "plaintext" that appears correct but is, in fact, wrong, by inserting specifically tailored "trash" data.

    3. Re:Public-Key vs. Secret-Key Crypto and P?=NP by adonoman · · Score: 1

      Which is why one-time-pad wouldn't work. But for any of the other "real-life" cryptosystems, manipulating the input to provide another viable decryption key with a chosen output would effectively mean cracking the system anyway.

  70. Secret-Key Cryptography would still work okay by billstewart · · Score: 1

    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.

    --

    Bill Stewart
    New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
    1. Re:Secret-Key Cryptography would still work okay by CTachyon · · Score: 1

      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 know the list of all 256-bit AES keys that satisfy that calculation. (Substitute "English" for any human language or binary file format you prefer.) You would still have the problem of sorting through all the candidate plaintexts, but if the ciphertext is longer than 256 bits then the list of candidates will be very short. Only one time pads (key length equals plaintext length) would remain truly safe if P=NP, because an n-bit ciphertext could represent any possible n-bit plaintext, i.e. the P=NP magic doesn't teach you anything you didn't already know.

      --
      Range Voting: preference intensity matters
  71. P=NP, really! by DJ_Perl · · Score: 1

    I am an amateur with a Computer Science degree, working on the Hamiltonian Cycle problem.
    Here's a site where you can try out my code. I will be releasing it under an open-source license this year.

    --
    -- Subvert the dominant paradigm. Repeat as desired. http://ownlifeful.com/
  72. Re:Nonsense - probably disprovable or maybe provab by garyebickford · · Score: 1

    Actually it will turn out that the solution to P = NP is in NP. :)

    --
    It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
  73. No More Secrets by Anonymous Coward · · Score: 0

    I already watched this film.

    It starred Robert Redford.

    And was in color.

    1. Re:No More Secrets by Anonymous Coward · · Score: 0

      "Setec Astronomy" was an anagram for "Too Many Secrets"

  74. Re:How come everyone in the movie is white? by TubeSteak · · Score: 1

    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?

    Racism doesn't have to be deliberate.

    And seeing how the sum total of the AC's comment was "How come everyone in the movie is white? Seriously."
    Maybe we need to ask why you think that comment implies that there is deliberate racism.

    If you're interested, there are articles and studies done on the statistical under representation of women and minorities in media and how this is reflected in the final product.

    --
    [Fuck Beta]
    o0t!
  75. Re:How come everyone in the movie is white? by slydder · · Score: 1

    Because this movie is so fundementally horrifying that the black guy died before they even started filming.

  76. Re:How come everyone in the movie is white? by nervouk · · Score: 1

    It probably was solved by a Japanese guy about 25 years ago, but like most of his countrymen he only spoke Japanese and wasn't able to communicate his solution to the outside world.

  77. Spoiler by arglefloggah · · Score: 1

    The final scene with the 4 mathematicians huddled around a blackboard, feverishly scribbling with chalk while a doomsday clock ticks away in he background. Then one turns around and whispers, “The answer is .42.”

  78. Oblig xkcd by kbob88 · · Score: 1

    Does the movie contain anyone ordering food in a restaurant like this?

  79. Re:How come everyone in the movie is white? by c9brown · · Score: 1

    Pfft... Dawkins? He just pretends he's as smart as everyone else by being ultra smug.

  80. A white man's world by Anonymous Coward · · Score: 0

    Wow, according to this trailer, all computer scientists are white men. In fact, everyone in the trailer is a white man. That certainly doesn't make me want to see the movie.

  81. Re:How come everyone in the movie is white? by Half-pint+HAL · · Score: 1

    Oh, you see, you're resorting to personal attacks because you can't argue against his massive intellect.

    Because everyone knows that you can't argue against something that doesn't exist.

    Except Dawkins, who spends his entire life arguing against something that he says doesn't exist.

    It's not like he's got anything better to do with his time, though -- he's only a biologist.

    --
    Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
  82. Re:How come everyone in the movie is white? by Half-pint+HAL · · Score: 1

    Nor do I know where the AC was getting his info, but he's right and you're wrong. IQ is highly heritable. WP has a detailed article on this. Reference 7 in the WP article is to a 2004 meta-analysis that puts the heritability figure at about 85% (meaning that heredity explains about 85% of the variance in adult IQ).

    Correlation is not causation. Latest news from the causation camp is that they have found the "intelligence gene". However, they say it's only responsible for 1.29 IQ points. That's 1.29% , not 85%.

    --
    Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
  83. Re:How come everyone in the movie is white? by Half-pint+HAL · · Score: 1

    I disagree with this statement. Intelligence is mostly controlled by your genes, it isn't even disputed in the science community. Has nothing to do with how you were raised.

    "mostly controlled by genes", probably. "nothing to do with how you were raised", not true. The reason that the twins/adoption studies evidence isn't more widely discussed is that it is of zero practical use -- it tells us people are different, but it gives us no insight into how to identify or deal with different types of people.

    A medical analogy (I don't drive, so I don't do car analogies).

    There are two diseases. One won't kill you unless you attempt to treat it with aspirin. One will kill you unless you treat it with aspirin. Other than that, the symptoms of the two diseases are identical.

    Until some clever doctor works out how to tell the two apart, there's nothing that can be done.

    --
    Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
  84. Re:How come everyone in the movie is white? by bcrowell · · Score: 1

    Correlation is not causation.

    Some of these are studies of twins raised separately by people other than their biological parents, which basically makes them immune to this objection.

    Latest news from the causation camp is that they have found the "intelligence gene". However, they say it's only responsible for 1.29 IQ points. That's 1.29% , not 85%.

    Nobody is claiming they've found "the" gene for intelligence. You seem to be misinterpreting what you've read, or maybe what you've read is a popularization that misinterprets the science. The fact that a particular gene only explains a small amount of variance doesn't mean what you seem to assume it means, which is that there are no other genes affecting intelligence.

  85. Re:How come everyone in the movie is white? by mark-t · · Score: 1

    The phrasing of the statement appears to imply a rather disgusted tone, which, in turn, implies that some sort of unspoken racist intent must have been at work.

    It's not like I was the only one who read his statement as some sort of notion that he was suggesting that the makers may have been biased against certain people based on the color of their skin... and while I realize that such appeal to the majority does not necessarily make me right, it does seem to make my conclusion one that it is not unreasonable in that regard.

  86. Re:Maybe they should solve by mcswell · · Score: 2

    And in my neck of the woods, travellling.