I was in graduate school (for the second time) when Alan Sokal pulled off his controversial hoax.  The fame it generated and the shame it heap upon the postmodern academic movement flared up for a brief time.  Unfortunately, based on a recent article by Peter Dreier, it seems that any lessons learned from it were lost of many academics. Fortunately it made a lasting impression on me.

For those who aren’t familiar, Sokal, a physicist at NYU specializing in quantum field theory and quantization of gravity, wrote an article for the social studies magazine Social Text, an academic journal that prided itself on being a champion of postmodern thinking.  In his article, entitled Transgressing the Boundaries: Towards a Transformative Hermeneutics of Quantum Gravity, Sokal attacks the very basis of the Western scientific method. His opening paragraphs read

and

For those who don’t have the stomach to wade through that gibberish (let alone what followed), what Sokal is trying to say is that scientific principles and results depend upon the culture and class from which one comes. He backs up this assertion by blurring the meaning of the Copenhagen interpretation of quantum mechanics into saying that the essential role of observer brings a social or cultural aspect to all science.

After the publication of this ridiculous nonsense, Sokal publicly announced that his article was a hoax. His aim in perpetrating this hoax was to demonstrate both the lack of rigor in certain academic circles and the clear introduction of bias if the writing appealed to the editorial slant of the journal. In his own words, Sokal said that he undertook this bit of hokum in order to see if a leading journal of cultural studies would

An example of these very preconceptions is on display in the discussion where Sokal cites Madsen and Maden who, according to the article, have two criteria for distinguishing between modernist and postmodernist science. Their criteria for postmodern science are:

1. it be free from any dependence on the concept of objective truth
2. it be constructed from those theoretical elements which are essential for the consistency and utility of the theory.

Earlier this week, Peter Dreier came clean about a similar hoax he had pulled-off in 2010. In his article entitled Confessing my sins and exposing my academic hoax, Dreier describes writing a sham abstract for a social studies panel on the “Absence of Absences”. In his narrative, he talks about how he wanted to see if he could write pure gibberish and still get it accepted to an academic conference. About the abstract that got him an invitation to the conference being held in Tokyo, Dreier says

After describing his flirtation with obfuscation, Dreier goes on to show that the desire by certain academics to indulge in abuses against the language is, by no means, limited to his little jaunt. He cites several cases of overly complicated postmodern phrasing which desperately tries to mask silly ideas with “academic pomposity”. In one particularly biting paragraph, he says

I applaud both Sokal and Dreier for making a vivid point about what sometimes passes for academic thinking in institutions of higher education but I can’t help but feel that they miss a bigger point. In both of their critiques, the notion of postmodern thinking is held up as an object of ridicule. But pointing out the ‘silliness’ of the postmodern logic isn’t enough. Sokal actually comes fairly close (whether accidentally or intentionally I don’t know) to what I am advocating in his treatment of Madsen and Madsen’s criteria for a science to be regarded as postmodern. Sokals passage shows, without explicitly stating so, the inherent contradictions of postmodern thought.

Briefly summarized, postmodern points-of-view use objective truths and logical tools built upon them, to try to prove the lack of objective truths. Each of the arguments rests firmly upon the unspoken and unrecognized assumptions that words mean something, that conclusions have a decidable truth value, that arguments supporting these conclusions can be logically derived, and that the argument put forth is objective – that is to say anyone of any culture will agree with the conclusions.

So how can postmodernism logically argue against logic? It can’t. It just isn’t consistent – and that is the real lesson of these hoaxes.

Several months ago, I wrote about the proof, due to Richard Kaye of Birmingham University in 2000, that the seemingly innocent-looking game Minesweeper is an example of an NP-Complete problem.  The essence being that no algorithm for solving the problem is known that scales as a polynomial function of the board size.

I suppose that it was inevitable that analysis of this sort would be extended to a host of other games.  After all, most computer scientists no doubt enjoy gaming as much as they enjoy computers.  In addition, unless there is some odd aspect of computer-scientist biology, each of them was once a child and, undoubtedly, was captivated by play.  But it was with a particular satisfaction that, after aimlessly wandering across the internet, I discovered the charming paper entitled Classic Nintendo Games are (Computationally) Hard.

This paper, written by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta, is an exploration of five of the classic 8-bit Nintendo franchises:  Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon.  Using an approach much like what Kaye used in his analysis, Aloupis et al examine the generalized form of each of these games.  A generalized form means that the size and structure of an individual board is open to manipulation but that the basic rules of the game are not altered.  Rooms take on arbitrary sizes and configurations and the number of non-playing characters (NPCs) can be unlimited.  Other than these liberties, the underlying mechanics of the game is maintained.

Now, I will confess that I never sunk much time into Donkey Kong, Legend of Zelda, or Metroid (much to my regret) and that I had only a passing flirtation with the Mario franchise, but Pokémon is a different story.  I’ve spent countless hours with that franchise and don’t regret a minute of it.  So, I thought I would discuss a little of how Pokémon can be thought of as NP-hard.

The first and most primitive notion is what Aloupis et al call the ‘decision problem of reachability’.  This is a rather big and forbidding name for a basic problem that almost every gamer has asked himself during gameplay:  ‘Given where I am and my current status can I reach that spot there?’  This is a particularly familiar problem in such large and open worlds like Elder Scrolls V: Skyrim.

The image below is an actual screenshot from Skyrim, where a player encounters a dragon on a mountaintop.  Because this meeting is essential to the storyline, the game limits access to the summit until the player has completed certain changes in status (i.e., solved a number of puzzles or quests, etc.).  Of course, the player doesn’t know this when the game commences and often the question as to whether the player can find a way up to the summit is left undecided until the plot advances to the point where the way becomes clear.  The mountains that appear in the distance remain undecided for many players throughout their interaction in the game.  They don’t figure in the plot and their accessibility is unknown unless the player manages to reach the peak.  In absence of such a feat, the player has to conclude the answer as ‘maybe’ – thus showing how art imitates real life.  I am sure that even the developers are not sure what answer to give.

Fortunately, the Pokémon games, being 2-dimensional worlds, are much simpler.  But not so simple that the paper by Aloupis et al is a trivial read.  In fact, I found it to be quite difficult in the sense that the framework being used is familiar only to the specialist and I have neither the time nor the inclination to get completely up to speed.

Instead, I would like to convey the flavor of it in terms of a Pokémon player.  The general idea about ‘decision problem of reachability’ is captured in the game mechanic familiar to anyone who has ever played Pokémon, the NPC enemy trainers.

For those of you who are unfamiliar or who simply want me to define my terms carefully, here is a quick summary.  In Pokémon, the player takes on the role of a young trainer who has in his possession between 1 and 6 pocket monsters.  His goal is to level up his Pokémon primarily through engaging in battles with other Pokémon either wild or in the possession of other trainers.  As the player roams the world, he encounters other trainers who, if the conditions are right, challenge the player to a battle.

Each enemy trainer possesses a set location, a direction in which he faces, and a line-of-sight. There are two ways to trigger a battle with an enemy trainer.  First, the player can ‘sneak up’ on the enemy trainer by moving next to him without entering his line-of-sight.  Talking to the enemy trainer initiates the battle but leaves the NPC in its set location.  Second, the player can walk through the enemy trainer’s line-of-sight.  The moment the player enters a space within the line-of-sight his motion is stopped and the enemy trainer moves from his set location to challenge the player.  Alternatively, a player may choose to avoid the enemy trainer by either avoiding talking to the NPC or not entering his line-of-sight.  This latter option is not always available.

Depending on which choice the player makes, certain areas in the game become accessible or inaccessible as the NPCs move to open or block certain spaces.  This behavior, when generalized, is at the heart of the proof by Aloupis et al.

The basic structure of their analysis is the creation of certain playable scenarios, called gadgets.  There are 6 gadgets that they use to prove NP-hardness: Start, Finish, Variable, Clause, Check, and Crossover.  The precise nature of these gadgets is involved, so I’ll only touch the Variable gadget as it is easy to understand.

The Variable gadget’s purpose is to provide the player with a single choice that flips a switch between two positions.  The construction Aloupis et al provide is

The red rectangle indicates the line-of-sight of the enemy trainer and the set location of the trainer is (2,4) (2^nd row, 4^th column from the upper left – denoted by the caricature of a man with glasses in a lab coat).  A player entering at a has two choices.  First, the player may choose to sneak up on the enemy by taking the top fork and beating him in battle, thus leaving the exit at c open.  Second, the player may choose to take the bottom fork, forcing the enemy to come down to (3,4) to battle.  Winning the battle then leaves the exit at b open.

The other 5 gadgets are constructed with similar elements and mechanics but often they are larger and more complicated to understand.  And the details are not all that important unless one wants to understand the technical details.  Rather, the basic message is that even cloaked behind the guise of a game, even ones as fun as the five famous Nintendo franchises analyzed, logic and decidability are all around us.

One of the curious traits of modern life is the fact that our ever-increasing advancements in technology, brought on by our application of reason, walk hand-in-hand with our ever-increasing disillusionment with faith.  To understand why this situation should be considered curious, we must first look at what the mainstream attitude is to these trends.

Common knowledge asserts that there is nothing curious about this at all, that such a progression is as it should be, and that only the most unscientific of us continue to cling to faith.  Those of our fellow beings who consider themselves intellectually sophisticated generally liken the poor souls ‘who still believe’ to our ‘modern’ conception of ‘primitive’ man – a being possessing a feeble mind that is inclined to believe that the world is administered by sylphs, dryads, titans, and gods.

A classic example of this dismissive thinking about how faith is antithetical to reason is the movie Contact. A strawman argument from beginning to end, this ‘measured’ exploration of why faith and reason are at odds is about as intellectually complex as a 30-second commercial for beer.  A thin patina of meaty-sounding, semi-respectable platitudes are trotted out as a way of disguising the vapid content of the arguments.  And to top it off, there isn’t even any good eye-candy in the movie.

So clearly, I think that faith and reason, rather than being at odds, are complementary aspects of human discovery.  But how can I possibly hold such a position without being branded as a poor, intellectually bankrupt soul who clings to outmoded ideas through sheer desperation?  By using the tools of reason to examine reason – that’s how.

There are two, closely-related ways of seeing this point-of-view.  The simplest is also, paradoxically, the most controversial and emotionally charged.  But since it is straightforward, it is the best place to start. In a nutshell, science is a fundamentally faith-based enterprise that is predicated on two articles that science itself cannot observe, measure, or classify.  The first article of faith is that the world is understandable.  This is the implicit assumption that went unsaid in the pseudo-intellectual’s critique of primitive man – that the world is not populated by magical creatures that affect changes on a whim.  The second scientific article of faith is even more remarkable.  It says that the experiment that one does in the here-and-now is applicable to the there-and-then.  In a world largely driven by change, it is something of a philosophical leap to say that the change is changeless.  True that the seasons progress but always in the same way.  Summer follows spring; never the other way round.  The sun rises and sets, but always in the same fashion and within changeless variations associated with season and latitude.  Were this not true, science would lack all it predictive power.

If you aren’t happy with this simpler argument that then note that the scientific enterprise is based mostly on inductive logic.  The experimenter conceives and performs an experiment.  Data of a limited sort is gathered and subsequently analyzed.  The results are generalized to abstract from this particular experiment to all similar situations or even (if one is of the caliber of Newton) to the universal.  The generalization works from a preponderance of observations to make a probabilistic syllogism:

It is true that once a general theory is put forward, predictions can be deductively obtained that then can be falsified with new experiments but the theory can never be proven with certainty that results from a deductive syllogism.   Thus, science is ‘stuck’ depending on inductive logic.

As Harry Gensler points out in his book Introduction to Logic, inductive logic is always on a shaky footing.  There are lots of problems.   One big problem is just how the generalization is made; either too narrow or too broad a generalization makes the probabilistic syllogism fail (I guess we need Goldilocks generalizations).  Occam’s razor is some help here but it is clearly not a scientific principle in that its justification can’t be based on empiricism – just what should be measured or observed to support the principle itself?  Its utility is based on how well it seems to work when constructing scientific theories but it falls into a meta category (unless perhaps applied to artificial intelligence).

Another problem is that inductive logic can’t prove or argue for itself.  Pretend for the moment it does.  We might then be inclined to construct the probabilistic syllogism that reads

Circular logic results since we need to assume inductive logic is true to show that inductive logic well supported.  In and of itself, this situation is not any different than trying to use deductive logic to prove itself.  At some level the tools of logic become self-referential and the argument falls apart.  The standard appeal is to take certain principles as self-evident truths.  For example, modus ponens works because it leads to sensible results.  So we adopt it and use it.  But this is a matter of faith – just because it has never failed doesn’t mean it won’t at some point.

So the only rational conclusion is that science, rather than running from faith, seems to have worked by running towards it.  The only confusion that results is simply due to the fact that the faith it runs towards just that is doesn’t look like the ‘faith of our fathers’.

I recently had a chance to read Socrates Meets Machiavelli:  The Father of Philosophy Cross-Examines the Author of the Prince, by Peter Kreeft.  Kreeft is a faculty member in the Department of a Philosophy, Morrissey College of Arts and Sciences, at Boston College.  He is well-known as a Christian Apologist and, by his own words, is a teacher and not a great philosopher.  Nonetheless, I’ve found many of his works to thought provoking and well-argued as any good philosopher should do.  Even when I don’t agree with his conclusions I can see how he got from point A to point B why he would lean the way he did.

In Socrates Meets Machiavelli, Kreeft attempts to make a modern-day Socratic dialog out of an imaginary meeting between the two titular characters in some limbo after both have died.  The work is intellectually stimulating but ultimately it fails at achieving the form and function of its more celebrated predecessors.  Even though Kreeft’s writing is not as poetic or skilled as Plato’s, the reason for this dialog falling far short is that there is a sense that Kreeft has his thumb on the scale from the start when the two characters meet.

To understand this point, consider Plato’s classic work The Euthyphro, in which Socrates meets up with the title character outside the Athenian courthouse.  Socrates is there to face the charges that would lead to his death.  In contrast, Euthyphro is there to accuse, not to rebut an accusation.  Both are Athenian citizens meeting on common ground.  Yes, Socrates is clearly the smarter of the two and he is far more artful in demonstrating the holes in Euthyphro’s arguments than the latter is in filling them.  Despite that, Socrates doesn’t win in the dialog – he simply succeeds in pointing out that the truth is far more elusive than Euthyphro would like to believe.

From the start, the meeting between Socrates and Machiavelli is of a different cast.  Consider the following exchange about 4 pages in

From this early stage Kreeft establishes the position of authority and power of Socrates over Machiavelli.  As a result, the entire work feels more like a polemic and less like a pursuit of truth; more of a monologue by Socrates to teach Machiavelli the error of his ways rather than a dialog in which both separate error from fact.

Nonetheless, the book is well worth reading if for no other reason than the structured approach that Kreeft’s uses to analyze philosophy and ethics and the strong conclusions that follow from its use.  In the interest of full disclosure, I am self-taught in my philosophical pursuits so, to the professional (which Kreeft, in his lecture course Ethics: A History of Moral Thought, points out is a bit like being an intellectual whore), maybe the following point is pedantic.  Still I will pluck up some courage and put it forward.

Until digesting Kreeft, I had looked at the fundamental base of philosophy to be built from ontology (the study of what the world is or the study of being) and epistemology (the study of what can be known).  Kreeft makes a subtle but powerful division of ontology into two pieces: anthropology, here defined to be the study of the human being; and ontology, defined to be the study of the being of what remains.  Ethics then finds itself at the intersection.

Of course, divisions of these sorts are artificial in that how we know what we know and why we know it is as much a function of who we are as people as it is a function of what is out there to be known.  This division is not unlike the quantum mechanical division between system, environment, and observer.  All are made from the physical world and are inextricably linked and yet it is useful to draw boundaries in order to understand.

And understanding is the great reward that comes from reading Socrates Meets Machiavelli.  No matter where one stands on the ethics questions raised in the text or whether one agrees with Kreeft, there is no denying that he makes a powerful argument that the practical man is a philosophical man.  That there is simply no way to succeed in the here-and-now without first deciding on firm meta-physical principles and then applying them is a central message; a message that makes one’s investment with this book worthwhile.

I forget exactly where I heard this, who said, or who it was about.  All I remember about the pithy little saying I am about to express (rather than continuing to allude to it) is the laughs that it caused.  I was driving along listening to some show about politics when one of the commentators suggested that some member of the government was ‘often wrong but never in doubt’.

Once my laughter faded – a process that took some time as that gem struck my funny bone – I began to reflect not only on the truth that was being conveyed but also why it worked that way.  So many of our most prominent citizens, from all professions, seem to not understand just what logic is all about.

The examples are so numerous that I’ve begun to filter them out to the point where I can’t even cite a specific one.  But the scenario is quite clear.  A media figure cites a study that, perhaps, mildly suggests that item A and item B are correlated and runs with it to suggest that A causes B.   A politician takes the words of another politician out of context, twists and turns them this way and that, and ends by constructing something with exactly the opposite meaning.  This typically occurs in its most egregious form when there are big stakes on the line, the kind that engender large emotions, but it isn’t confined to that.

The effect is quite clear but, what about the cause?  Now, if I am not careful, I’ll end up doing exactly what I am criticizing – drawing sweeping generalizations supported by a paucity of data but a lot of belief.  So let me say simply that I think that what causes wrong conclusions walking hand-in-hand with little or no doubt is that it is uncomfortable to deal with the doubt.

Each time we try to make an inductive argument we are dealing, whether formally or not, with statistical data and probabilistic inferences.  As Harry Gensler points out

Deductive reasoning is an all or nothing undertaking.  Everything is locked down, certain, and the outcomes are never in doubt.  The rules for proceeding from premises are established and have no room for negotiation.  The application can be in error but sufficient effort always results in valid reasoning.  The only open question is the soundness of the argument, which hinges on whether the premises are true.

In contrast with deductive arguments, inductive ones generally get murkier as data are added. Certainly a sufficient number of observations are needed to grasp a pattern, but too many observations begin to undermine it.  In addition, patterns are simple when they involve one or two variables but as the number of considerations grow so too do the number of combinations, each with its own rule.  Inductive arguments always take the form of statistical syllogisms that works most cleanly the less we know.  These arguments may not be reliable (the analog to sound) but they can be quite strong (the analog to valid) if the probabilities we assign to the premises are high.  This is most easily done if we don’t have a host of additional factors making exceptions here and there.

Gensler provides a nice example of this point using college football and I want to give him full credit for a good teaching device.  That said, I will present its flavor only after having switched to professional football.

Suppose we know, having analyzed the total plays called by the Pittsburgh Steelers, that 80% of the time they throw the ball deep on a second and short yardage situation when they are at least 30 yards from their own end zone.  Suppose, also that we see during this Sunday’s divisional playoff game between them and the Denver Broncos, that the Steelers have 2^nd-and-3 down with the ball on Denver’s 47-yard line.  We can reason thus:

This seems simple enough, but Gensler often adds to this form the additional line that reads ‘This is all we know’.  At first glance this may seem to be superfluous but as the next example shows, saying that we want to limit our facts may actually beneficial.

Suppose we know, again from the sample of plays, that the Steelers run 70% of the time when they are ahead by at least 10 points.  Now if we knew nothing about down and distance but knew that they were winning 20-3, we might reason

So far so good!  But now consider that the score is 20-3 and that they have the ball on Denver’s 47-yard line in a short-yardage second down.  What should we conclude?  Do they run or pass.  Perhaps they should just punt.  Now layer in additional considerations like the time left in the game, weather conditions, and critical injuries and the situation really gets complicated.

And this is exactly why I think that there is such a correlation between certainty and intellectual short-sightedness.  It is easier and more comforting to focus on a single aspect of a complex scenario, find a pattern and merciless apply it.  The result is a logic ostrich, with its head in the sand, comforted that it can’t see the messy possibilities.  Socrates was right – the only wisdom is in knowing that one is not wise (although it is possible that an ostrich is still better looking than Socrates).

The genesis of this post was some time off that I finally took from work and the chance to sit down and play some videogames and relax.  In the process of playing an old favorite and then discussing it with my friends I got a new appreciation for some of the subtle points of how language and thinking shape each other.

To set the stage, I must confess that many years back, I willingly allowed myself to be swept-up by the Doom craze.  I recall that when the free sample came out a lot of guys at work (me included) loaded up the game as a diversion from the code-slinging the powers-that-be demanded.  A few scant years later found me in possession of Doom and Doom 2 and the corresponding Battle Books (walkthroughs with a much cooler name) and having spent countless hours dodging imps, cacodemons, and the like.

Fast forward nearly 20 years (sigh…) and similar scene is now playing out again, although in a different residence and on a quite different platform.  Gone was the old DOS-based, Windows-running Pentium machine I spent over $2000 to buy.  In its place is a sleek, black PS3 which cost about a tenth of that price with decidedly more graphics and computational horsepower.  Gone are the old CD-ROM versions of the games, each requiring a lengthy installation.  In its place is a DVD bearing the name Doom: BFG Edition (I wonder – what does BFG stand for?) containing Doom’s 1-3; each capable of starting up right out of the box with no installation.  Both changes are improvements to be sure.  Unfortunately, not everything was an improvement.

After playing the original Doom on the PS3 for a short while, I began to become very irritated with the awkwardness I was experiencing.  Certainly a large portion of that was initially due to my rust and age.  After all, two decades had passed since I regularly played arcade and first-person shooter type games, and my hand-eye coordination was not as fresh and sharp.  But my expectation was that the irritation would fade as I got more practiced and that expectation was not met.

Upon some reflection (once my adrenaline had dissipated), I realized that it was a particular game mechanic that was getting in the way.  In the original Doom, which was released for the PC, the developer had a vast number of input keys/devices to choose from.  The keyboard alone offers over 100 different keys, including the arrow keys.  Throw in a mouse and one has a potent set of device combinations to map to the game mechanics.

The situation is quite different on the PS3.  While it is true that the two analog sticks each offer full 2-degrees of freedom, they are almost always reserved for in-game translation and rotation.  That leaves only 14 keys for interacting with the cyber-environment with the triangle, square, circle, and ‘x’ being the primary ones.

For much of Doom’s game play, which is primarily moving, turning, and shooting, the smaller number of key’s is not an impediment. The place where the mechanic breaks down is weapon selection.  At the start of the game, your character is simply armed with… well his arms.  As the game progresses, additional weapons are acquired, each with its own strengths and weaknesses.  During battle with a host of foes, you need to be able to switch weapons smoothly to maximize you lethality and minimize your chances of dying.  On the PC, weapons-switches happened by selecting a number key in the range 1-6, inclusive.  Selecting ‘1’ meant you were using bare knuckles, ‘3’ was the shotgun, and ‘6’ meant you were yielding the BFG (there’s that abbreviation again – I wonder…).  In the PS3 version, random access of the weapons list is replaced by an awkward cycling through of the weapons in one direction by repeatedly pressing the circle button.

It is really hard to select the correct weapon while being attacked and, even when it is calm, it is easy to accidently go past the weapon you want and have to circle back to get it.  Speed and fluidity are hallmarks of Doom and this method of switching weapons really detracts from feeling immersed in the game.

This is a case where the language betrays the message; a case where how the idea is expressed is a road-block to the idea itself.  It is an example of a user-interface metaphor that simply doesn’t work.

Often we don’t notice when the metaphor expressed in a user-interface is good.  That is as it should be, with the language (the particular button sequence being used) cleanly expressing the intention (the actions on the screen).  But we clearly notice when the metaphor is bad.  It sticks out like a sore thumb.

As a user community we’ve even come to expect compromised or even bad metaphors from software we need to use.  Examples here range from mandated applications at our work, or programs we use as a means to an end (e.g. tax preparation software).

But within the context of gaming, a bad metaphor can’t be ignored. After all, the purpose of the game is to have fun.  If the metaphor is bad it lessens or even destroys the fun.  Since the game is the end and not the means to another end, there is no way to justify awkwardness of expression.  This conclusion holds broadly for much of how we use language.  We will slog or way unhappily through an obscurely written tax form or government regulation simply because we must.  But we will reject an unartfully constructed joke or an awkwardly written story.  In the case of the videogame, we get to see the whole phenomenon work in a highly compact and specialized language – the language of buttons, joysticks, symbols, and lights and shadows played out on a screen.

A couple of weeks ago, I explored the notion of computational complexity and how amazing amounts of complexity can show up in seemingly simple contexts.  In the particular case examined, the Subset Sum problem, the familiarity of the simple activities of ‘looking’ and ‘adding numbers’ masks a surprising conclusion that an algorithm that scales as a polynomial in time is most likely impossible to find.  The Subset Sum is said to be an NP-Complete problem.

Computational complexity can be lurking in even tamer and more familiar guises.  One of the more innocent-looking locations is in the simple computer game that comes with Windows – Minesweeper.

Before talking about the formal aspects of how Minesweeper is NP-Complete, let’s look at how the complexity arises from a practical example.  For simplicity, I’ll be looking at three separate cases drawn from the beginner’s level of Minesweeper.

In all cases, one starts with zero information as to the placement of the mines and so the first move is always a blind-luck guess.

If it works out, one gets information about the number of mines in the eight nearest-neighbor spaces.  If one is lucky, the information is enough to solve the puzzle outright.  Case 1 is such a case.  After one successful blind guess, the information available on the board was sufficient to get to the end stage where it is obvious how to solve the puzzle

The two remaining mines need to go directly next to the ‘3’ and the ‘4’ and so the remaining two spaces can be explored without fear.

Sometimes, no amount of logic can save you and there is nothing to do but guess as in Case 2.  After the initial blind-guess the board looked like

Solving for the obvious spaces leads to the final configuration with two unexplored spaces and one remaining mine.  No amount of deductive or inductive logic will save the day and a 50/50 guess is required (for those who care, I guessed wrong).

Both of these cases have the luxury of being straightforward.  The amount of thinking was kept to a minimum and the options were well understood (although not always successfully so).

The true complexity of the game becomes apparent in the in-between Case 3.  After the blind guess and resolution of the easy spaces, the board looked like this:

There is no way to easily finish off the board but nor is the final solution up to chance.  It is a matter of exploring possibilities.  Since ‘1’ spaces are easiest to deal with, let’s focus on the line of three ‘1’s found on the lower right.  Let’s tentatively mark the rightmost ‘1’ as having a mine directly below it by placing a ‘?’ on the space.  Making that assumption leads to a propagation of other possible mine spaces, each marked with a ‘?’, as shown below

The entire set of ‘?’s is consistent – that is to say, we don’t have a contradiction anywhere.

Next suppose that we assume a mine just below the middle ‘1’ on the row of three on the right.  Putting a ‘?’ there leads to an inconsistency, since if there is a mine at the location of the ‘?’ there is no way to satisfy the ‘1’ and ‘2’that are next to each other.  The red dot (which is photo-edited in since Minesweeper doesn’t provide a marker for inconsistency) drives this point home.

Similar logic holds for putting the ‘?’ under the leftmost ‘1’ and so the only consistent guess was the first one.  Acting on that guess leads immediately to success.

The true complexity of Minesweeper becomes obvious upon reflection of what can happen when the field is bigger and the number of mines is increased.  Each blind luck move at the beginning of the game can lead to numerous possible avenues to explore.  Each ‘?’ placed on the board can spawn additional channels to explore; the difficulty can grow exponentially.

This argument is a plausible, heuristic one so there may be a tendency for the reader to respond ‘But you really haven’t proven it!’.  That is a point I am willing to concede – I haven’t proven it – but someone has.

In the spring of 2000, mathematician Richard Kaye of Birmingham University was able to prove that Minesweeper is NP-Complete.  This means that Minesweeper is a decision problem (did you solve it or did you detonate), it is very hard to find a solution, and it is very easy to check the solution.  He also went on to construct various logic gates in Minesweeper and using these, proved, in 2007, that Minesweeper played on an infinite board with infinite mines (although fewer mines than spaces) is also Turing complete.

So the next time someone chides you for wasting time playing Minesweeper, respectfully point out that you are not wasting time, you are researching one of the most important open questions in computer science.

One of the central questions about linguistics asks how much thinking influences language and how much language, in turn, influences thinking.  Clearly there is a link between how we express a thought and what the thought entails.  The words we know, the familiar phrases we invoke certainly shape how others perceive our expressed thought; but what of ourselves?  How much of a feedback loop exists wherein the manner in which we express a thought influences how that thought is perceived by the ourselves is unknown.  Each of us plays the role of both speaker and listener when speaking and often how we express ourselves influences how we perceive ourselves – at least as we imagine how we are perceived by through others eyes.

Clearly there is a link but measuring that link and determining which direction is strongest (thought to language vs language to thought) is ephemeral.  Natural language has been around for so long and with no formal metrics kept until what is essentially yesterday in terms of the march of history that it seems nearly impossible to find out much by examining everyday speech.  Much like the fish that lives in the ocean, we are often even unable to see the medium of speech in which we swim since it is so pervasive.

Mathematical languages have offered better laboratories.  Formal mathematical expression is relatively young – perhaps 500 years old – and is continually refined.  By examining the evolution of mathematics, both the thoughts codified and the method used for the codification, a consensus has been reached that the form of the expression is often as important as what is being expressed.  Why else are there what amounts to holy wars over mathematical notation.  The camps of Newton and Liebniz often warred with each other over the best way to denote the calculus.  Friction of this sort continued on into the 18^th and 19^th centuries with arguments over vectors and quaternions, sets and logic, and so on.  The general observation is that that better notation means better thinking.

This sentiment is also very much alive and well in the equally contentious ‘discussions’ about which programming language is best.  Adherent s on all sides will talk about the advantages and disadvantages that each has but, regardless of the particulars, one thing is clear; each programmer thinks his favorite language provides him the best avenue to express his thought, while simultaneously holding that other languages limit just how a programmer even thinks about how to solve a problem.

In a nutshell, all three disciplines – linguistics, mathematics, and computer programming – possess practitioners, who at one time or another, expressed the old proverb:

Unfortunately, all three of these disciplines pre-date modern big data metric collection and analysis.  But there is a modern language-and-thinking loop that is amenable to quantitative analysis.  Each and every day, millions of web-enabled searches are performed.  Some are looking for news, some researching information, some surfing for gossip, some rummaging for products or services, but all are getting auto-completion tossed there way.

It would be interesting and revealing to see to what extent auto-completion influences how we think.  I am sure each of us has started typing a search string into Amazon or Bing or Google only to find ourselves distracted by an auto-completion that was suggested by other searchers.  Surely these entities have the data and probably are sitting on it for commercial purposes but whether they are looking at it from a scientific point-of-view is unknown – although the probability is against it.

Perhaps there is a sociology or psychology department out there that can craft a well-thought out experiment, complete with control and test groups, where they ask students to perform research on the internet in support of a course.  The students are then given two identically-looking search engines.  The test group would get an unmodified search engine and the test group on with a different approach to auto-complete; maybe with more suggestive or more distracting completions relevant to the stated research goal.   Once the data were reduced and analyzed new insights into how to understand the way language and thought interact would be available.  These insights may then shape how we think about thinking, and so on.

One can’t really be alive, work with computers, writing algorithms to solve hard problems, and be ignorant of the importance of a good algorithm.  Most texts on scientific programming, which formed the bulk of what I read in my formative technical years, possess at least on cautionary tale about how slow a computation can be if the algorithm is bad.

One classic tale I like, which is often trotted out with gusto, is the calculation of the Fibonacci numbers.  As a reminder, the nth Fibonacci number is the sum of the two previous ones

\[  F_n = F_{n-1} + F_{n-2} \; . \]

So to compute $F_{100}$, one need to compute $F_{99}$ and $F_{98}$, each of which need the two below them.  Computing naively causes a lot of repetition since one computes $F_{98}$ and $F_{97}$ to compute $F_{99}$ and $F_{97}$ and $F_{96}$ for $F_{98}$ and so on.  Of course, a fast algorithm exists which essentially involves recording these values once computed, thus ensuring that they are computed only once in the recursion.

While compelling, this cautionary tale is a bit of a cheat.  Someone actually knows the best algorithm and it happens to be quite fast and, generally speaking, it isn’t all that interesting to compute the Fibonacci numbers oneself, since they are immutable.

Much more interesting are the situations that are dynamic.  Finding the best route to visit an arbitrary list of cities is the stuff of legends with which the famous Traveling Salesman Problem (TSP) wrestles.  This problem is often listed as hard, or rather NP-Complete, a class of algorithms that belongs to the larger class of NP-Hard problems.

Roughly speaking, NP problems (or which NP-Complete and NP-Hard belong) are computational problems that do not possess known algorithms that can find solutions in polynomial time.  What that means is that as the input data set, usually thought of as consisting of $N$ entries, is increased (i.e. $N$ grows) the computing time required to find a solution grows much fasters than any polynomial in $N$.  Usually the growth is exponential, although worse cases, such as combinatorial growth, also occur.  This is in sharp contrast with the P class of computational problems that do possess known algorithms that can find solutions in polynomial time.

The curious thing about NP problems are that while they are not quickly solvable, they are quickly checkable.  This phrasing means that while it takes a long time to find a solution for a large input data set, once the solution has been found it can be verified in a relative short period of time that scales as a polynomial in $N$.

This distinction is hard to understand and this difficulty is compounded by the fact that the NP class has three qualifiers making for NP, NP-Complete, and NP-Hard as well as containing the P class.  In addition, problems like the TSP are very specialized and complex making them very hard to relate to in general

Note: The reason NP-Hard lies partially outside the NP boundary is because some NP-Hard may not even be decidable. Undecidable problems possess no definitive answer to the computing question with which they are posed.  That such problems exist inescapably follows from Turing’s analysis of the halting problem.

So I searched for a simplified problem that I could sink my teeth into.  A problem that would be tractable enough to play with but still demonstrated the ‘NP-ness’ in a way that I could relate.  After some trial-and-error, it seems that Subset Sum Problem (SSP) fits the bill.

The SSP asks the following question.  Given a sum $S$ and a set of integers $Q$ is there a proper subset of $Q$ that sums to $S$.   It is provable that the SSP is NP-Complete:  a solution exists (i.e. the problem is decidable) ; it is hard to find a solution, especially when $Q$ has a lot of elements; and it is easy to check the solution once the answer is revealed.

That the SSP is decidable is actually trivial to see.  Given a subset $P \in Q$ of integers, it is easy to sum them together and to test whether the result equals $S$.  By playing with a simple configuration for $Q$, it was easy to demonstrate that it is hard to just find a subset that sums to the desired value and that is equal easy to check once an answer is proffered.

Consider the following $3 \times 4$ block of integers between 1-9, inclusive.

The sum of all of them is 53 and the smallest number in the set is 1, so it is also easy to answer no to the SSP when $S$ is outside this range.  But what about the rest of the values?  Can any value between 1 and 53 be represented?  (It should be clear that 1 is represented trivially by one of the 1s in Q and that 53 is represented by the whole set).

For a test, can we find a subset that sums to 19?  That answer is obvious if one stares at the grid for a while.  Since there is a 9 in the grid, all one needs to find is two numbers that sum to 10 in order to demonstrate that 19 is a valid subset sum.  One such possibility is

How should we go about answering the general question?  This is where the NP part comes in.  In general, the best algorithms known are not polynomial in complexity.  I won’t try to prove this; I am simply stating the conclusion of the computer science community.   But being NP, it is easy to check that a proposed solution is valid in polynomial time.  For example, it may not be obvious that 47 is contained as a subset sum within the grid but the following shows it to be true

Each of the blocks of different shades of red sum to 10 (i.e.: 6 + 4; 9 + 1; 8 + 2; 5 + 4 + 1) and the light orange block is a 7. Checking that solution is easier than finding it in the first place or in finding an alternative (note that one trivial change can be done in 3 cell to get a different set that subset sums to 47 – hint – look at the blocks that remained white).

Now back to the general question as to whether any sum can be constructed.  Consider the grid now colored so that the red subsets sum to 30 and the white portion of the grid consists of the numbers 1, 2, 3, 4, 5, and 8.

Since the numbers 1, 2, 3, and 4 can sum to every number on the range 1-10, we already have that all numbers from 1 to 40 are subset sums.  For example, 27 can be formed from the two pairs of tens (say 1 + 9 & 7 + 3) and from 3 + 4.  Finally since 8 + 2 = 10 and 8 + 3 = 11, the remaining sums from 41 through 52 are also achievable.  Thus we have proved that all values between 1 and 53 are achievable.

Note that the time it takes to confirm any of these values is much shorter than the time it would take an algorithm to find these solutions.  That is what it means to be NP-Complete.

I recently came across an interesting method for combining qualitative and quantitative data on a common footing to allow for a mathematically supported framework for make complicated decisions where many criteria are involved.  The method is called the Analytic Hierarchy Process.

The Analytic Hierarchy Process (AHP), which was invented Thomas L. Saaty in the 1970s, uses a technique based on matrices and eigenvectors to structure complex decision making when large sets of alternatives and criteria are involved and/or when some of the criteria are described by attributes that cannot be assigned objective rankings are in play.  It is especially useful in group-based decision making since it allows the judgements of disparate stake-holders, often with quite different points-of-view, to be considered in a dispassionate way.

In a nut-shell, the AHP consists of three parts: the objective, the criteria, and the alternatives.  Criteria can be sub-divided as finely as desired, with the obvious, concomitant cost of more complexity in the decision making process.  Each alternative is then assigned a value in each criterion and each criteria is given a weighting.  The assessments are normalized and matrix methods are used to link the relative values and weightings to give a ranking.  Graphically, these parts are usually presented in hierarchical chart that looks something like:

A nice tutorial exists by Haas and Meixner entitled An Illustrated Guide to the Analytic Hierarchy Process and this posting is patterned closely after their slides.  The decision-making process that they address is buying a car.  This is the objective (‘the what’) that we seek to accomplish.  We will use three criteria when selecting the car to buy:  Style, Reliability, and Fuel Economy.

Two of these criteria, Style and Reliability, are qualitative or, at least, semi-qualitative, whereas the Fuel Economy is quantitative.  Our alternatives/selections for the cars will be AutoFine, BigMotors, CoolCar, and Dynamix.

The first step is to make assign numerical labels to the qualitative criteria.  We will use a 1-10 scale for Style and Reliability.  Since we are weighing judgements, the absolute values of these scores are meaningless.  Instead the labels indicate the relative ranking.  For example, we can assume that the 1-10 scale can be interpreted as:

• 1 – perfectly equal
• 3 – moderately more important/moderately better
• 5 – strongly more important/strongly better
• 7 – very strongly more important/very strongly better
• 9 – extremely more important/extremely better

with the even-labeled values slightly greater in shading than the odd labels that precede them.  This ranking scheme can be used to assign weightings to the criteria relative to each other (for example style is almost strongly more important than reliability – 4/1) and to weigh the alternatives against each other in a particular criteria (for example AutoFine is moderately better than CoolCar in reliability).

To be concrete, let’s suppose our friend Michael is looking to buy a car.  We interview Michael and find that he feels that:

• Style is half as important as Reliability
• Style is 3 times more important as Fuel Economy
• Reliability is 4 times more important as Fuel Economy

Based on these responses, we construct a weighting table

where the first number in the entry corresponds to the row and the second to the column.  So the ‘4/1’ entry encodes the statement that Reliability is 4 times more important as Fuel Economy. The omitted entries below the diagonal as simply the reverses of the one above (e.g. 1/2 goes to 2/1).

This table is converted to a weighting matrix $\mathbf{W}$ which numerically looks

\[ {\mathbf W} = \left[ \begin{array}{ccc} 1.000 & 0.5000 & 3.000 \\ 2.000 & 1.000 & 4.000 \\ 0.3333 & 0.2500 & 1.000 \end{array} \right] \; . \]

In a similar fashion, we interview Michael for his judgments of each automobile model with each criteria and find corresponding weighting matrices for Style and Reliability:

\[ {\mathbf S} = \left[ \begin{array}{ccc} 1.000 & 0.2500 & 4.000 & 0.1667 \\ 4.000 & 1.000 & 4.000 & 0.2500 \\ 0.2500 & 0.2500 & 1.000 & 0.2000 \\ 6.000 & 4.000 & 5.000 & 1.000 \end{array} \right] \; \]

and

\[ {\mathbf R} = \left[ \begin{array}{ccc} 1.000 & 2.000 & 5.000 & 1.000 \\ 0.5000 & 1.000 & 3.000 & 2.000 \\ 0.2000 & 0.3333 & 1.000 & 0.2500 \\ 1.000 & 0.5000 & 4.000 & 1.000 \end{array} \right] \; . \]

Finally, we rank the fuel economy for each alternative.  Here we don’t need to depend on Michael’s judgment and can simply look up the CAFE standards to find

\[ {\mathbf F} = \left[ \begin{array}{c}34\\27\\24\\28 \end{array} \right] mpg \; . \]

Saaty’s method directs us to first find the eigenvectors of each of the $4 \times 4$ criteria matrices and of the $3 \times 3$ weighting matrix that correspond to largest eigenvalues for each.  Note that the Fuel Economy is already in vector form.  The L1 norm is used so that each vector is normalized by the sum of it elements.  The resulting vectors are:

\[ {\mathbf vW} = \left[ \begin{array}{c}0.3196\\0.5584\\0.1220 \end{array} \right] \; , \]

\[ {\mathbf vS} = \left[ \begin{array}{c}0.1163\\0.2473\\0.0599\\0.5764 \end{array} \right] \; , \]

\[ {\mathbf vR} = \left[ \begin{array}{c}0.3786\\0.2901\\0.0742\\0.2571 \end{array} \right] \; , \]

and

\[ {\mathbf vF} = \left[ \begin{array}{c}0.3009\\0.2389\\0.2124\\0.2479 \end{array} \right] \; . \]

A $4 \times 3$ matrix is formed whose columns are ${\mathbf vS}$, ${\mathbf vR}$, ${\mathbf vF}$ which is then left multiplied into ${\mathbf vW}$ to give a final ranking.  Doing this gives:

So from the point-of-view of our criteria, Dynamix is the way to go.  Of course, we haven’t figured in cost.  To this end, Haas and Meixner recommend scaling these results by the cost to get a value.  This is done straightforwardly as shown in the following table.

With this new data incorporated, we now decided that BigMotors gives us the best value for the money.  Whether our friend Michael will follow either of these two recommendations, is, of course, only answerable by him but at least the AHP gives some rational way of weighing the facts.  I suspect that Aristotle would have been pleased.