Magic, NP-Complete Problems, and Mathematical Modeling

Let’s begin by taking an illustrative example. You might have seen a magician perform a trick in which he mysteriously makes a coin disappear from one hand and makes it appear on the other. The trick goes something like this:

The magician sits across the table from you. He first asks the audience to observe complete silence. He then performs some mysterious rituals, and then lays down both his hands on the table, with both the palms open and facing upwards. He asks you to take out a coin from your pocket, have a close look at it so that you could identify it later on. He asks you to keep that coin on the open palm of one of his hands, say the right hand. He then slowly closes his eyes, and begins to chant a mantra. Soon his body begins shaking, and even as this is continuing, he turns his palms downwards, clenching his fists in the process. Continuing with chanting of mantras, he now slowly opens his eyes and begins to concentrate hard, alternately on either of his hands, as if commanding something invisible to move something. Even as you are watching intently, he slowly begins to fold his palms even as they are still kept touching the table, and thus begins to form clenched fists. The chanting of the mantra now proceeds even more rapidly, at an almost feverish a pace. The look on his face is deep concentration personified. This goes on for a while. Slowly, the pace of the mantra intonation slackens, and soon afterward, he ceases the chanting of the mantra altogether. He then relaxes. After a while, slowly, he opens his palms and holds them open in front of you. Your coin is now visible on the left hand side—not on the right hand side!

Magic!!

In disbelief, to prove him wrong, you take his palms in your hands and make sure there is no such a thing as a skin-colored glove or a mask. You check the sleeves of his shirt. You look under the table cloth. Why, you also go and look below the table. … All, in vain. Finally, you give up.

Your friends suggest some more possibilities. You are too tired to check them out. So, your friends now take charge. They too go through some of your own checks and them some more. No use. Eventually, you all give up. You are not willing to admit that the coin might have traveled using some supernatural means of transportation—or via some quantum-mechanical principles that can never be understood, as per your favorite physics professor. You are not willing to admit either of these. Or any such a similar thing. And yet, you have no solution either—no idea what’s going on here.

. . . . .

Undoubtedly, you would be aware of the Millennium Problems posed by the Clay Mathematics Institute. A lot has been written on these problems since they were announced at the turn of the millennium… Why, recently, the Institute even offered the very first Millennium Prize, for having successfully solved the Poincare conjecture problem, to a Russian mathematician called Gregory Perelman.[^]

What concerns us here is the as-yet-unsolved problem of P-vs-NP.

This is a problem from the computational complexity theory. A good introduction to this theoretical area might be had by visiting the Wikipedia page on “Computational Complexity Theory” [^], and the one on the  “Traveling Salesman Problem” [^].

The introductory material for the description of this problem, as given on the Web page of the Clay Institute itself, includes the following:

In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure.

Most writers trying to explain this brand of mathematics have used a similar language, emphasizing the inherent asymmetry between solving a problem and checking or verifying the solution.

For example, consider the domain of encryption. Given an encrypted text, it is hard to find what the original text might be. You might try different combination of letters and symbols as a password, and use it in a trial decryption, but without success. The “brute force” method of trying out every possible password may take forever, simply because there are so many combinations possible. However, if you are given the password—i.e. the solution—then, it is very easy to verify that it works for decryption. That is to say, it is very easy to verify that the given solution indeed is a solution. Similarly, for the Traveling Salesman Problem. It is easy to verify that a given route has a cost that falls below a given specific value, and yet, it’s difficult to find the routes that would fulfill the given cost constraints.

The popular mathematics writers, therefore, often emphasize this asymmetry in their writing.

While this way of characterizing this kind of mathematics is as good as it gets, it can also give rise to some misconceptions.

For example, consider the magic trick given above. The problem is to determine and explain whether the coin at all goes from one hand to the other, and if yes, how. This problem is extremely difficult to solve for any lay person. … If it weren’t, there would be no element of mystery left in it, there won’t be any magic left in it! Yet, if a solution—an explanation of how the magic trick actually works—is given to you, it would be very easy to verify that that’s what is going on. Let me proceed to tell you just that.

. . . . .

The coin does physically go from the palm on the right to that on the left—there are no optical illusions involved here. However, the coin does not so physically shift as a result of all that mental concentration or the mantra-chanting.

As an aside: This does not mean that consciousness cannot move matter around. We all routinely do so for the matter in our brain when we are doing anything like thinking, lifting an arm, or even dreaming. … Hat tip to Dr. Harry Binswanger [^], for his lectures on the metaphysics of consciousness. [I knew it already, but he puts it far more clearly than I could have.]

Coming back to the magic. Certainly, the coin does not move because of the hard mental concentration of the magician. In fact, it does not even move after be begins to concentrate! The coin has already moved from one palm to another way before that! Read the whole sequence of the trick once again, in particular, this part appearing right at the beginning of the description:  “… He then slowly closes his eyes, and begins to chant a mantra. Soon his body begins shaking, and even as this is continuing, he turns his palms downwards, clenching his fists in the process. …” What the magician actually does is to flick the right hand palm a bit too quickly, and a moment too early as compared to the left palm, in the process of his turning the palms downward. In that flick, he is actually tossing the coin—right in front of your eyes—from the right palm to the left. Since the action is so quick—and done so smoothly—you don’t notice it. … The chanting of the mantra and the closing of his own eyes etc. are all diversions designed to attract your attention away from that flick. Another related matter: Any object that streaks past your eyes at a close distance is not registered too well. Try that game of rolling a cricket ball over your arm, and giving it a jerk with your elbow. Instead of you catching the ball, have a friend nearby, and ask him to catch the ball. It is tough. Not because the ball is moving fast, but because not just the direction of the flick but also its timing is difficult to anticipate. And this happens even if your friend knows in advance that you are going to flick the ball. … What happens when you don’t even know that flicking the coin right through the air above is what that magician is going to do!! It’s next to impossible to tell that the coin has been flicked through the air—if you don’t already know the solution.

. . . . .

So the magic trick seems to fit the description for the NP-category of problems. I mean the parallels seem to be obvious, at the first glance. For this magic trick, as for a typical NP-complete/hard problem, the solution is difficult to get at—there are just too many other possibilities that you would have to exhaust one by one. But the solution, if it is already known, is very easy to verify.

Does that mean that this magic trick is in NP?

Nope. Not at all.Not if you are careful in your choice of words.

The problem of P-vs-NP is a very specific problem of mathematics that has been defined in a very careful manner. Just because some characteristics of this problem also apply to magic does not mean that magic is in NP. Indeed, taken by itself, this statement does not even begin to make sense.

To be able to apply the theory NP problems to magic, one will have to first create an abstract model capturing the essentials of this particular trick. One will have to show that it can be modeled in terms of, e.g., the graph theory, as nodes connected via edges. Each of the different possibilities existing for putting the coin in the other palm would have to be shown as a possible route via certain abstract nodes and edges. Further, one will have to demonstrate that logically and quantitatively, this graph model of the magic trick satisfies all the essential characteristics displayed by the NP category of problem. It is only then that anyone would be able to do anything mathematically useful with this idea. Otherwise, it is just a surface analog and nothing more.

An aside: Unlike many, perhaps most, mathematicians (and a large number of physicists too), I believe that analogs and analogies by themselves are not bad—they do not represent inexact or sloppy thinking just because they are analogies. The trouble is, analogies often are poor in that they only scratch the surface and do not continue showing analogous relationships at even deeper, more fundamental, levels. Without analogies, you couldn’t gain insight about, say, electricity, starting from, say, ideal fluid flow. Analogies are useful, nay, even important. Provided that the analog continues to hold even in some fundamental way.

. . . . .

We have seen how you have to build an abstract model of a physical situation before it can be mathematized. There is a symmetrical counterpart to this procedure too.

Often times you find mathematics being admired for its “direct” application in physics. For example, chaos theory in fluid turbulence, or even more popularly, hypergeometry in the relativity theory.

I believe that when mathematicians say something like that, many times (though not always) they are actually engaging in a fallacy—what I call the fallacy of Hasty Application. (To the best of my knowledge, such a fallacy does not actually exist. I just made it up. It is meant to be a fallacy which is symmetrical to the existing fallacy of Hasty Generalization. Actually, a closely related fallacy of Hasty Concretization should also be possible.)

What mathematicians ought to be doing in instances like these—if they at all wish to concern themselves with applications (which they should!)—is to carefully spell out the structure and the meaning of the abstract physical model which they have assumed in so applying their favorite mathematical theory. [… It’s too much to ask of today’s mathematicians, I know…]

Abstract models do not always have to be mathematical, they can be also physical. Stronger: For proper integration, when it comes to applying mathematics to physics, you have no choice but to first find the corresponding abstract physical model(s). Today, both the physicists and the mathematicians have abdicated this responsibility. Yet, by the grace of reality—i.e. the nature of the human consciousness—explicitly identification of the abstract physical model is a necessity. It is a necessity for the proper acquisition, validation, or application of knowledge.

A physical theory cannot be “done” just by giving some equations, say together with their units. A theory is not another name for a “cheat-sheet.”… Ultimately, truth is not established in reference to mere mental constructs; correspondence has to be established to the perceptual facts of reality.

That is what is involved in applying a mathematical theory or idea to some aspect of the physical reality. Too many mathematicians—and mathematics-lovers—stumble on this part.

If you don’t spell out the sense in which you are using the term “light,” and “matter,” if you don’t specify what you are already assuming towards the nature of the interconnections between these  in your theory (or completely abstain from ever mentioning that anything of this sort is at all being taken for granted in such a BVP/IVP view of reality), if you don’t specify what the referents for your notion of space, time, or “spacetime” are, and then, without poring over any such a matter if you brazenly go ahead and say that your favorite theory of hypergeometry is important because it is “directly” applicable to Einstein’s relativity, you are merely confessing either your ignorance or your incompetence in the matters of what it takes for a piece of mathematics to be applicable to an aspect of reality. And worse. It takes no brains to tell that you are using hypergeometry precisely because it helps you forward your favorite nonsensical, bizzare, convoluted ideas of nothingness wrapping and turning within itself as being physically real.

Even if mathematicians were to simply provide the meaning of all the essential concepts in a theory, say hypergeometry and relativity, I would be happy. I wouldn’t ask them—though this part, too, is necessary—to begin with hypergeometry’s relation to ordinary geometry and then do the same for the physical theory and demonstrate how the contents of that physical theory actually neither contradict nor surprise the common-sense. I wouldn’t expect them to do this second part, primarily because if the physical meaning of the concepts is known, if the physical model is well identified in the first place, then almost anyone could do the second part. It is the first part which is difficult. And it the first part where mathematicians (and physicists, not to mention irrationalists) play all their magician’s tricks.

. . . . .

Though I don’t have the patience left to type out any more, think about this in the meanwhile:

Taking a typical example of the category of problems that are well-modeled as NP-complete/hard problems (e.g. , the Traveling Salesman problem), it is very easy to see that there indeed are a large number of alternative paths possible. These problems, as we have seen, satisfy the difficult-to-solve-but-easy-to-verify criterion.

Then, as we saw for the case of the magic trick, it too satisfies the same difficult-to-solve-but-easy-to-verify criterion. Yet, observe that, in this problem, the number of alternatives (or possible solutions) are very few.

Indeed, even though it is known that this problem is difficult to solve, the said difficulty does not very easily manifest as the greatness of the number of possibilities.

Further, even alternative paths are not easy to isolate or conceive of, given just the physical observation of the trick. Each formulation of the hypothesis for the solution, by itself requires a great degree of acuteness of observation, ability to form coherent and reasonable hypotheses… All in all, the scientific kind of creativity.

In contrast, in the mathematical NP problems, stating the alternatives available is as simple as mechanically enumerating them—it involves no creativity.

Observe that today’s mathematicians (and, unfortunately also today’s physicists, theoretical engineers, etc.) lionize the second but not the first.

…May be, more on some of these aspects, later…

– – – – –

Songs I Like [More or less at random]

1. (Hindi) “nayi manzil, nayi raahen…”
Music: Hemant Kumar
Singers: Lata Mangeshkar and Hemant Kumar
Lyrics: S. H. Bihari

2. (Hindi) “teraa meraa saath rahe…”
Music: Ravindra Jain
Singer: Lata Mangeshkar
Lyrics: Ravindra Jain (?)

– – – – –

PS: As usual, to be improved/streamlined…

Advertisements