Skip to content

Magical Results and P=NP

October 11, 2009


Which is more likely: intractable problems or magical results?

kruskal

Martin Kruskal was a famous mathematician who won many awards for his work in diverse areas of applied mathematics. He is perhaps best known, among his peers, for his important joint work with Norman Zabusky; work which helped start the soliton revolution. He is also known among magicians, for a brilliant illusion that is called the “Kruskal Count.” See this memorial page about Kruskal for a list of his accomplishments.

Today I want to talk about some other magical aspects of mathematics. One of the great things about mathematics is that often there are results that seem to be “impossible.” Magical.

I was at Princeton’s Computer Science department at the same time that Kruskal was in their Mathematics department. I still remember making a “small” contribution to Princeton’s attempt to lure Michael Rabin away from Harvard. As is often the case when recruiting a senior super-star like Rabin, they had a group dinner at a quite good local Chinese restaurant. Since I knew Michael well I was invited to join them.

We had our own private room at the restaurant. It was a lovely meal: delicious food and great conversation. When the dinner ended, after we all had read our fortune cookies, Michael and others stood up and began to say their goodnights to each other.

I was still sitting next to Martin, who was in charge of our dinner. He proceeded to pull out a hand-calculator, and started to figure out what we each owed as our share of the bill. I was a bit surprised, since in computer science the tradition was to have the department pay for the whole dinner—after all it was an official recruiting function. But each department has its own rules.

Martin started to calculate, after tip, what each of the group of twelve owed for their dinner. I started to get my wallet out so I could pay my share, when I realized that Martin had included Rabin as one who would be paying. I gently suggested to Martin that perhaps we could treat our “guest” and divide not by 12 but by 11. Martin liked this idea very much, and re-calculated the new figure that we all owed.

Rabin never did accept an offer to come to Princeton, but I like to think that the switch to dividing by 11 instead of 12 could not have hurt.

Kruskal’s Count

Here is the trick, or the illusion as my magician friends prefer to say.

The trick uses an ordinary deck of cards. Each card has a value: an ace is {1}, all picture cards are {5}, and the rest have their face value. Thus, a king of diamonds is {5} and a three of spades is {3}. The deck is shuffled, really shuffled. No trick there.

You are the magician and let Paul be the person you are trying to impress with your mind reading abilities. You tell Paul to pick a secret number {x} that is between {1} and {10} and to not tell you the number. Then, as you deal the cards, one by one, you ask Paul to do a simple count: For example, if his secret number was {2}, then as you show the cards Paul should count to {2} and see what the value of the second card is. That is his new secret number. He then does the same thing as the next cards are revealed. At all times he is counting and replacing his secret with a new secret. Paul does all of this in his head, keeping his secrets to himself.

When the deck runs out, you think hard. Then, you announce the secret that is in Paul’s head. Amazing.

How It Works

The critical part of the illusion is that you cannot guess what Paul’s original number {x} was. That would be real mind-reading. If you can do that, then you should head directly to Las Vegas and play high-stakes poker.

The key is that you, the magician, pick a number {y}, and do the same process as Paul does. The brilliant insight of Kruskal is that there is a good chance that at some point you and Paul will select the exact same card. Once this happens, then you and Paul are in synch and will continue to remain in synch. So at the end you just announce what your secret is and it will be the same as Paul’s with about {85\%} probability. Very neat.

Magical Results

There are many other magical results throughout theory. I plan a longer post on a list of my favorite ones. For now I want to discuss one of the great discoveries of Computer Science, that is one can turn “lemons into lemonade.” If there are hard functions, “the lemons,” that cannot be computed efficiently, then magical things can happen, the “lemonade.” Turning lemons into lemonade is one of the key insights of modern cryptography.

I will not even begin to attempt to give a survey of the many great results in this area, but I do have a point that is related to my favorite question: “can P=NP be true?”

Close you eyes for a moment, and then take a deep breath. I am going to ask you to imagine two different scenarios:

In the first one, suppose Alicex is an alien from Mars and has just arrived on Earth. She knows some mathematics, but no modern complexity theory or cryptography—Mars has not yet been able to develop it. She is told that the following two things are possible here on Earth:

  1. She can send a perfectly secret message back to her friends on Mars; even though Alicex has no secret bits in common with her friends back there. On Mars they have one-time pads, but nothing better for sending secret messages. Alicex is surprised.
  2. She is also told that we, I mean Andrew Wiles, has been able to prove Fermat’s Last Theorem:

    \displaystyle x^{n} + y^{n} = z^{n}

    with {n>2} implies that {xyz=0}. Of course Alicex calls this problem something else: the “Gozzetx Problem.” It is named after the famous Martian mathematician Fredx Gozzetx, whose elegant proof that every planar graph has a four coloring was one of the great achievements of early Martian mathematics. Every Martian high school student knows his famous proof.

    This is a welcome news. But then Alicex is told that she can convince her friends back home on Mars that she knows a proof of this great theorem. And she can do this without giving away the actual proof. This is very neat, since there is a {\not{o}1,000,000,000} prize in Martian money for a proof. She trusts her friends, but that’s a lot of money; even with their recent inflation {\not{o}100} is still enough to buy what we call a mocha latte. Alicex is surprised.

In the second one, suppose that Bobx is also an alien from Mars and has just arrived on Earth. Bobx like Alicex knows some mathematics, but no modern complexity theory or cryptography. We tell Bobx that the following is possible here on Earth: there is an algorithm that can factor any integer in polynomial time. Bobx is surprised.

Open Problems

Which alien is more surprised? Alicex or Bobx?

One of the reasons I have doubts about P{\neq}NP is simple. I often wonder which is more surprising? That there could be an intelligent algorithm to solve a “hard” problem like factoring, or that there are magical results of modern cryptography? This is one reason I find the P=NP question so puzzling. Why is it so easy to believe that there is no clever algorithm for SAT, but that it is possible to do:

  • Public-Key encryption?
  • Signatures?
  • Zero-knowledge proofs?
  • And on and on?

These seems like magic to me. What do you think?

28 Comments leave one →
  1. FK-MAI permalink
    October 11, 2009 11:20 pm

    “One of the reasons I have doubts about P{\neq}NP is simple. I often wonder which is more surprising? That there could be an intelligent algorithm to solve a “hard” problem like factoring, or that there are magical results of modern cryptography? ”

    I don’t think it’s a matter of which alien is MORE surprised…
    I believe that in the future we will have an answer concerning SAT problems – the answer might be an intelligent algorithm or a mathematical proof, of either P=NP or P{\neq}NP.

    Since the NP question remains without an answer, my intuition tells me that the solution is going to be magical!! If its not, well, i wouldnt like to be in the shoes of all the Computer scientists and mathematicians that tried to come up with an answer all these years… Out of respect for their work (and fear of being in their place), I must insist that we should expecting something magic….
    So,in your two scenarios, both aliens should be surprised, since not everything is about “what you do”, but also “how you do it”…. If Bobx (since he is the issue) is not surprised then, probably, in Mars they’ve never tried to answer the NP question..

    As for “Why is it so easy to believe that there is no clever algorithm for SAT..”….well, if there was, wouldn’t we know it until now? Its a matter of scientific/intelligence “arrogance”(for lack of a better word….).

    PS Congratulations for your blog….happy to find you

  2. JamesD permalink
    October 12, 2009 12:16 am

    There already is an efficient algorithm for factoring. No, quantum computers have not yet been fully implemented, but in a theoretical discussion, especially one that involves Martians, they cannot be ignored.

    • rjlipton permalink*
      October 12, 2009 6:17 am

      Good point. But perhaps since they do not have modern cryptography they did not have anyone working on quantum factoring.

    • Anonymous permalink
      August 10, 2010 6:56 pm

      Also, Bobx would presumably be less surprised because integer factorization is *not* known (or even generally suspected, AFAIK) to be NP-complete; Bobx could retain his belief that P =/= NP. On the other hand, I’m pretty sure that Alicex would have to give up her belief that P = NP in the face of the evidence in her story.

  3. anup permalink
    October 12, 2009 1:00 am

    The magicians strategy can be deduced from the properties of the trick (in hindsight): imagine that the trick is simultaneously performed on Paul and Polly, who each independently think of a secret number. Then the magician’s final answer must satisfy both of them, which implies that Polly must have the same secret at the end as Paul. So any such trick must have the same winning strategy (i.e. play the role of Polly). Of course, if the trick is only guaranteed to work 99% of the time, then the deduced strategy might work just 98% of the time..

    With regards to whether P=NP would be surprising.. I have begun to get the impression that there is a large but silent contingent of P=NP believers/plausibelievers. Maybe it’s just that the not equals crowd makes a bigger noise.

  4. October 12, 2009 6:53 am

    Anup says: I have begun to get the impression that there is a large but silent contingent of P=NP believers/plausibelievers

    If “actions speak louder than words”, then pretty much every mathematician, scientist, and engineer is a believer … because our empirical experience is that NP *is* in P.

    This applies to real-world problems like proof-finding, law-deducing, and design-optimizing.

    One empirical rule of “complexity aesthetics” is this: Proofs that are NP-hard to find are ugly proofs, physical laws that are NP-hard to conceive are ugly laws, and most of all, systems that are NP-hard to optimize are ugly systems.

    Conversely, don’t what Dick calls “magical results” have in common the surprise unveiling of unanticipated simplicity? And don’t we experience these results as being beautiful?

    • lylebot permalink
      October 15, 2009 1:53 pm

      Maybe this is just a function of how our brains work. We try to justify the fact that some problems are hard by calling the rare solutions we do find “ugly” and saying “we wouldn’t want to solve that anyway, it’s aesthetically displeasing!” I’m not sure I would agree that means they actually are aesthetically displeasing, assuming some Platonic ideal of aesthetics.

  5. October 12, 2009 9:45 am

    As a followup to the above, isn’t the most surprising kind of proof of a really ugly proof of a beautiful result?

    So much so, that if a theorem can be proved only by ugly methods, we tend to think it is maybe not such an important theorem?

    It’s tricky … the four-color map theorem is an example … did the Appel/Haken proof increase versus decrease the luster of the four-color theorem?

    Maybe it is safe to say that the jury is still out, and that much will depend on whether further proofs care developed that are simpler and/or more general in their domain of application.

    Nowadays, every principle that is true of mathematics is also true of engineering. Energy is beautiful … burning coal is ugly. Molecular biology is beautiful … benchtop experimentation is slow and crude.

    Engineers deal with these challenges in the exactly the same way as mathematicians: we raise the level of abstraction and we seek new forms of beauty … and that is why engineers are constantly prospecting in the literature of mathematics.

    Sometimes mathematicians make it easier for us — by writing clearly and gracefully … this mathematical blog (and a few others) are a *big* help … for which many thanks!🙂

    • rjlipton permalink*
      October 12, 2009 12:21 pm

      Thanks for your comments.

  6. anon permalink
    October 12, 2009 9:56 am

    John: “our empirical experience is that NP *is* in P.” is based on thinking that the P vs NP question is the same as “can we solve the TSP”. While that is a good rephrasing of the problem for the laymen, it is not quite the P vs NP question. In fact, an implication of NP being in P empirically would be that all crypto we know currently is broken empirically. I do not think that is the case.

  7. adam o permalink
    October 12, 2009 1:15 pm

    for what it’s worth, i’d like to comment that one of the major achievements of modern crypto is showing that “magical” examples like you mention are reducible to less magical tools, like a one-way function. my intuition for why one-way functions exist is that they have strong physical analogues… breaking an egg, mixing coke and pepsi, etc, seem to be examples of one way functions in the physical world.

    • rjlipton permalink*
      October 12, 2009 1:48 pm

      I like this analogy. I am not sure it dead on, but nice one. Wonder of could make really stronger analogy? Trouble might be at some level physical systems are invertible and that could be a problem. Not sure.

  8. richde permalink
    October 13, 2009 1:38 am

    This is a very nice way of thinking about it. I’ve heard versions of magical results in other fields too. The exactness of Ohm’s Law, for instance. I recall the highest praise from Paul Erdos who, upon hearing a result, would sometimes say “That’s not to be expected.”

  9. October 13, 2009 6:18 am

    There is a nice quote from Grothendieck too that relates to magical results: “The question you raise ‘how can such a formulation lead to computations?’ doesn’t bother me in the least! Throughout my whole life as a mathematician, the possibility of making explicit, elegant computations has always come out by itself, as a byproduct of a thorough conceptual understanding of what was going on. Thus I never bothered about whether what would come out would be suitable for this or that, but just tried to understand — and it always turned out that understanding was all that mattered. ”

    This suggests that a working definition: “A magic result demonstrates how the embrace of a higher level of abstraction and/or an alternative mathematical framework leads to magically simplified computations.”

    Magical simplification is the Holy Grail of engineering, and this is why engineers *love* both magical mathematical calculations *and* cool Grothendieck quotes about them.🙂

  10. October 13, 2009 12:07 pm

    Finding out that Factoring is in P would not be that surprising. Finding out that SAT is in P would be.

  11. Josh permalink
    October 13, 2009 5:48 pm

    Regarding John Sidles’s comment that “we” believe NP is in P, and anon’s seemingly contradictory comment that everyone using e-commerce believes P is not in P:

    These two comments are not in fact contradictory. In the case of engineers, and John points out, they explicitly look for the elegant problems. In some heuristic sense, elegant problems may correspond to easily solvable instances of SAT, TSP, etc. On the other hand, in the case of cryptographers, they explicitly look for hard instances of, say, factoring.

    This harks back to the discussion of a previous post: https://rjlipton.wordpress.com/2009/07/13/sat-solvers-is-sat-hard-or-easy/

  12. October 14, 2009 3:52 pm

    She can send a perfectly secret message back to her friends on Mars; even though Alicex has no secret bits in common with her friends back there.

    I don’t see how. A public/private pair would have to have been generated before she left, which doesn’t fit the story. She can’t negotiate a key via radio with Mars, because there’s no way to prevent man-in-the-middle attacks. She doesn’t need to share a secret key, but she does have to have made some prior arrangement for her friends on Mars to authenticate themselves during a Diffie-Hellman session key exchange.

    • rjlipton permalink*
      October 14, 2009 4:09 pm

      Why do you assume that she would have no way to authenticate herself. There are always middle attacks possible, but she might have a personal secret that she could use to solve that problem. I can also think that such attacks given they would be using radio or other directional methods might be quite a less of a concern.

      • Anonymous permalink
        August 10, 2010 6:51 pm

        Alicex did need to securely share some *information* with her friends back home before she left; she needed to tell them, “Hey, Charliex, my public key is KA.” However, that information does not need to be kept *secret*. Charliex is allowed to tell everyone that KA is Alicex’s public key; Charliex is even allowed to tell everyone the exact details of the conversation in which Alicex revealed her public key to him (and not just the final result).

        However, Alicex really does need to have had that conversation with Charliex at some point prior to her departure. Once Alicex is on Earth, Charliex shouldn’t trust any unauthenticated Earth broadcasts as coming from Alicex.

        Alicex doesn’t need to share a secret with Charliex, but she “does have to have made some prior arrangement” with him. Nevertheless, “Alicex has no secret bits in common with” Charliex, because the only bits she has in common with Charliex are *not secret*.

  13. Tetha permalink
    October 14, 2009 5:49 pm

    P = NP would surprise me very much, as it means that “guessing” provides no benefit anymore, if assumes a practically interesting equality.

    The guessing would be irrelevant, as nondeterminism would be not relevant anymore for time classes with at least a polynomial lower bound on them (and nondeterminism for space classes provides no benefit either anymore). This would mean, one could write algorithms like: Guess solution. Done.🙂

    Of course, I have some strong assumptions in here. For one, I assume that there is a tractable reduction for an NP-complete problem to a problem in P (and no proof which just shows “yes there is one. No, we don’t know how it looks.”), and also that the runtime of the resulting algorithm is somehow tractable (so there should no proof which shows that any polynomial time algorithm solving an NP-hard problem requires at least n^10000 steps, as then a simple EXP-Time algorithm is faster for a lot of inputs).

    But who knows? Ach, this is an interesting problem to think about, since there are so many possibilities and in my opinion, it is very possible that the result of P = NP (or not) will have no practical relevance (consider those n^1000-algorithms, or those 1.000001^n algorithms to solve problems in NP).

    But… as we all now: P = NP iff N = 1.😉 Regards, Tetha.

    • subruk permalink
      October 14, 2009 11:17 pm

      Interesting thought Tetha. Lipton has blogged about several possible outcomes of the P=NP problem. See here.

  14. papa permalink
    October 14, 2009 6:09 pm

    Hi.

    Could you please fill in “And on and on? “? Many of your listed things were new to me and I’d like to learn even more new things.

    Papa.

    • rjlipton permalink*
      October 14, 2009 6:45 pm

      There are many magical things that cryptography can do. You should be able to find many on-line. Here is a nice on-line summary of some. Some of the cool things are: (1) if Alice knows x and Bob y they can compute f(x,y) without either learning the others value; (2) voting in secret is possible as are auctions; (3) databases can be created that leak only the information that one wishes.

      Can also check out this site for election comments.

      Perhaps I should post on this more in the future. What do you think?

      I hope this helps.

  15. Smith Stuart permalink
    October 15, 2009 11:27 am

    Ok. This is as usual a well-written, fantastic and insightful post. I like everyone else who is reading this blog is very grateful for your stories.

    Having said that, I have to say that I am somewhat surprised that you had to actively propose to share the bill and not have Rabin pay. Shouldn’t that have been obvious ? With all due respect, the first time around I read it, I found Martin’s behavior kinda “cheap” in that respect. It should have come natural.

    • rjlipton permalink*
      October 15, 2009 5:05 pm

      I worried about this issue. I meant no disrespect. I tried to relate a story that I thought more showed the difference in cultures between math and CS at that time. That’s all. I hope that is what most understood.

  16. October 15, 2009 12:13 pm

    Which Chinese restaurant in Princeton did you take Rabin to?

    • rjlipton permalink*
      October 15, 2009 5:05 pm

      I think it is gone. But it was a small place next to the Amtrak station.

Trackbacks

  1. Is P=NP a reasonable hypothesis? « Constraints

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s