Magical Results and P=NP
Which is more likely: intractable problems or magical results?
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.
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 , all picture cards are , and the rest have their face value. Thus, a king of diamonds is and a three of spades is . 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 that is between and 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 , then as you show the cards Paul should count to 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 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 , 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 probability. Very neat.
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:
- 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.
- She is also told that we, I mean Andrew Wiles, has been able to prove Fermat’s Last Theorem:
with implies that . 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 prize in Martian money for a proof. She trusts her friends, but that’s a lot of money; even with their recent inflation 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.
Which alien is more surprised? Alicex or Bobx?
One of the reasons I have doubts about PNP 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?
- Zero-knowledge proofs?
- And on and on?
These seems like magic to me. What do you think?