The Fable of the Chessmaster
If a layperson asks you what computational complexity is, you could do worse than to tell the following story, which I learned from Steven Rudich.
A man with a flowing gray beard is standing on a street corner, claiming to be God. A bemused crowd gathers around him. “Prove it!” they taunt.
“Well,” says the man,”I can beat anyone at chess.”
A game is duly arranged against Kasparov, who happens to be in town. The man with the gray beard wins.
“OK, so you’re pretty good at chess,” the onlookers concede. “But that still doesn’t mean you’re God.”
“O ye of little faith! As long as I play White, it’s not just hard to beat me — it’s mathematically impossible! Play Black over and over, try every possible sequence of moves, and you’ll see: I always win.”
A nerd pipes up. “But there are more sequences of moves than there are atoms in the universe! Even supposing you beat us every day for a century, we’d still have no idea whether some sequence of moves we hadn’t tried yet would lead to your defeat. We’ll be long dead before every possibility is examined. So unless you’re prepared to grant us immortality, there’s no way you can possibly convince us!”
Most of you know the punchline to this story, but for those who don’t: the nerd is wrong. By asking a short sequence of randomly-chosen questions, each a followup to the last, the crowd can quickly convince itself, to as high a confidence as it likes, that the man they’re interrogating knows a winning strategy for White — or else expose his lie if he doesn’t. The reason was discovered in 1990 by Lund, Fortnow, Karloff, Nisan, and Shamir, and has less to do with chess than with the zeroes of polynomials over finite fields.
There are two lessons I’d like to draw from Rudich’s Fable of the Chessmaster.
The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They’re a great way to illustrate the point, they were probably essential for discovering the point, but they’re not the point.
The best definition of complexity theory I can think of is that it’s quantitative theology: the mathematical study of hypothetical superintelligent beings such as gods. Its concerns include:
- If a God or gods existed, how could they reveal themselves to mortals? (IP=PSPACE, or MIP=NEXP in the polytheistic case.)
- Which gods are mightier than which other gods? (PNP vs. PP, SZK vs. QMA, BQPNP vs. NPBQP, etc. etc.)
- Could a munificent God choose to bestow His omniscience on a mortal? (EXP vs. P/poly.)
- Can oracles be trusted? (Can oracles be trusted?)
And of course:
- Could mortals ever become godlike themselves? (P vs. NP, BQP vs. NP.)
Incidentally, it’s ironic that some people derisively refer to string theory as “recreational mathematical theology.” String theory has to earn the status of mathematical theology — right now it’s merely physics! A good place for string theorists to start their theological training is this recent paper by Denef and Douglas.
So that was my first lesson. The second lesson is that interaction helps: you can get your message across a lot faster if people are continually challenging you. If the gray-bearded man were just lecturing to a passive audience, rather than being grilled by doubters trying to trap him in a contradiction, then it would take longer than the age of the universe for him to prove his unbeatability at chess. Or rather, we theologians conjecture that it would.
I’m reminded of the power of interaction every time I give a talk. Despite a certain reputation for cheap yuks, I’ve never been a good speaker. I’m terrible at explaining anything coherently — that is, in a way that anticipates people’s objections. Fortunately, as long as people interrupt me, it doesn’t matter much, since I can easily answer the objections once I know what they are. Indeed, not only do interruptions clue me in on what’s bugging people — as in the Fable of the Chessmaster, they also let me prove that I basically know what I’m talking about, even if I can’t articulate it in the allotted time!
(In my ideal talk, I would begin by saying “Thank you. Are there any questions?”)
For another example, take the sex columnist Dan Savage. Savage has a “philosophy,” which consists partly of a refusal to condemn sex acts if they don’t harm anyone, and a willingness to condemn them if they do. But if he tried to state his philosophy explicitly, he wouldn’t do it justice any more than I just did. So instead he answers questions about used underwear fetishes and masturbating parakeets.
The same goes for comedians, at least the good ones like Jon Stewart. Stewart has an enviably easy job: news happens, he reacts to it. It’s like my ideal talk that consists entirely of questions — except that instead of questions, there’s Bush warning about “human-animal hybrids” in his State of the Union address, or Cheney shooting his hunting buddy in the face.
Inspired by such examples, and by my recent positive experience answering Peter Brooke’s question, I’ve decided to open this blog to questions on a regular basis. Email them, post them in the comments section, whatever. I can’t promise to take up everything. Try to guess which of the following would have a better chance:
“Please discuss the relative merits of conference and journal publication in theoretical computer science.”
“How could schools be redesigned to improve the sex lives of nerds?”
Follow
Comment #1 February 18th, 2006 at 10:54 am
Actually, isn’t it easier than that? Instead of playing the man’s game (“you can’t beat me at chess”), they could have just asked him any questions he should be able to answer from the start. Bringing up chess presupposes a problem that doesn’t even exist in the first place — that it’s “hard” to verify that a person is God, when the first instinct people would have is to ask him questions (What color is my underwear? What color was my underwear yesterday?), which is exactly IP.
I guess what I don’t like about this example is that it somehow says, “Oh, look at us complexity theorists. We have thought up things that people didn’t realize.” And of course you have, and there are actually *very* good examples of it. But I don’t think this is one of them.
I tend to like the example of convincing a color blind person that somebody else knows the difference between two colors. Now *that’s* impressive.
Comment #2 February 18th, 2006 at 11:04 am
open this blog to questions on a regular basis
Then, would you like to comment on Richard Cohen’s article in the Washington Post about the (un)importance of algebra?
We might as well say that the article needs no comment, but I’m sure you’d be able to come up with something really piquant, and I’d love to read it š
Comment #3 February 18th, 2006 at 11:54 am
For all we know there could be a clever strategy for chess that uses the special structure of the opening position to force a win and doesn’t require any godlike computations once you’ve dreamed it up. So even with an IP this guy would have trouble convincing some of us. God should be able to play perfectly given any old gnarly position.
But, throw in the result, due to Fortnow and Feigenbaum in
http://citeseer.ist.psu.edu/24505.html
that PSPACE is ‘random self-reducible’–for any PSPACE-complete set L, there is a fixed, efficiently computable distribution on instances such that an algorithm solving L on most of these can be converted to a randomized algorithm solving L on all inputs with high probability.
Now take a PSPACE-complete game like n x n checkers; by sampling from such a distribution on board positions and asking the man for interactive proofs of the win/loss status of each, you can be convinced of his robust mastery of the game (and, perhaps, the universe).
Comment #4 February 18th, 2006 at 1:47 pm
Wouldn’t it be far more expedient for the gray-beard to demonstrate a collision in sha1? (Yeah, yeah, sha1 may be busted, but in principle a secure hash function should be usable for this purpose.)
How about algorithms in the polynomial-time heirarchy? The distinction between quadratic and quasilinear runtimes for multiplication would appear to be a squabble among mortals, with no actual gods involved.
Comment #5 February 18th, 2006 at 2:05 pm
Do you consider k-agreement to fall within computational complexity? How about TCP backoff algorithms? And the current (completely non-rigorous) study of block ciphers?
Comment #6 February 18th, 2006 at 3:06 pm
If you ever write a popular book on complexity theory, this is the angle to take. Title “On Distinguishing the Gods, and becoming Gods” or some such.
Comment #7 February 18th, 2006 at 3:47 pm
The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They’re a great way to illustrate the point, they were probably essential for discovering the point, but they’re not the point.
This is a perfectly valid and sometimes healthy point of view of complexity theory, but it is also sort-of pompous and only one side of the truth. Complexity theory both is and is not about computers.
On the one hand, it is, as you describe it, a branch of pure mathematics that happens to be modelled by computers. But it is also an intellectual backdrop of computers, indeed to some extent the intellectual backdrop that you need to truly understand computers.
The historically first and most important example is that you need complexity theory to define what a computer is, in other words what distinguishes a computer from another electronic device such as a DVD player. The defining trait, of course, is Turing universality. To some extent, your claim that computers are essential to see the point of complexity theory is historically backwards. Complexity theory, as represented by Turing and von Neumann, was necessary for inventing computers.
You could say that all of that is water under the bridge, that at least modern complexity theory is pure mathematics and not applied mathematics. That is somewhat true, except that in order to do applied mathematics, you have to have mathematics to apply. Just last week I had lunch with an astronomer who is writing scheduling software for a planned expensive new telescope. His problem is a variation of the Travelling Salesman Problem. The subtleties of P and NP were clearly important to his situation. In particular, the result that even approximate TSP can be NP-hard given a low enough fudge factor.
Even the analogy with clocks and special relativity goes in this direction. If you restrict attention to the very precise clocks that can detect special relativity, then indeed, you need special relativity to understand them. You have to use special relativity to properly design and maintain GPS, or the rest of the world’s system of atomic clocks.
Comment #8 February 18th, 2006 at 3:50 pm
Then, would you like to comment on Richard Cohen’s article in the Washington Post about the (un)importance of algebra?
It would be a bit redundant, since the man has already offended half of the mathematically literate end of the blogosphere.
Comment #9 February 18th, 2006 at 4:27 pm
how powerful can we expect god to be?
can he do superliminal signaling? defy the laws of logic?
can’t we just put god in checkmate and then ask him if he can still win?
perhaps scott’s point is that we can actually distinguish gods much lower in the diety hierarchy.
Comment #10 February 18th, 2006 at 4:35 pm
clearly it might have at least helped mr. cohen to learn what constitutes a “proof.” from the article:
Writing is the highest form of reasoning. This is a fact. Algebra is not. The proof of this, Gabriela, is all the people in my high school…
(proof by anecdote now follows)
and ironically, this is exactly why valid reasoning is a vital skill in the real world. at the very least so that you don’t spend all of your money buying crap from informercials, or paying taxes to the republican government that you elected.
Comment #11 February 18th, 2006 at 4:40 pm
Anonymous 4:27:
how powerful can we expect god to be? can he do superluminal signaling?
Maybe, as long as he can also change the past.
defy the laws of logic?
Not according to St. Augustine.
perhaps scott’s point is that we can actually distinguish gods much lower in the diety hierarchy.
Thank you! Thank you! That’s my answer to anonymous 10:54.
Comment #12 February 18th, 2006 at 4:51 pm
here is a question.
isn’t the real problem with complexity theory that the resulting mathematics is usually superficial and shallow?
does this make it less fun to do complexity theory?
are complexity theorists ever saying something deep?
Comment #13 February 18th, 2006 at 4:52 pm
Greg:
To some extent, your claim that computers are essential to see the point of complexity theory is historically backwards. Complexity theory, as represented by Turing and von Neumann, was necessary for inventing computers.
No, what’s striking is that Turing and von Neumann didn’t invent complexity, even though they could have! They had a formal theory of computation, and they had some notion of efficiency (how couldn’t they?), but they didn’t put the two together.
I consider complexity theory to have “started” only in the 1960’s, even though its motivating concerns arguably go back to antiquity.
Comment #14 February 18th, 2006 at 4:59 pm
Anonymous 4:51:
isn’t the real problem with complexity theory that the resulting mathematics is usually superficial and shallow?
does this make it less fun to do complexity theory?
are complexity theorists ever saying something deep?
Are you trying to provoke and enrage me into blogging about this? If so, you’ve probably succeeded.
Comment #15 February 18th, 2006 at 5:17 pm
Bram:
Wouldn’t it be far more expedient for the gray-beard to demonstrate a collision in sha1?
Maybe, but that’s not what H/he offered. š Anyway, we should at least be able to choose a hash function that the graybeard didn’t know in advance. That would rule out the case that he’s “merely” a prophet who talked to God sometime in the past.
Comment #16 February 18th, 2006 at 5:22 pm
Bram:
Do you consider k-agreement to fall within computational complexity? How about TCP backoff algorithms? And the current (completely non-rigorous) study of block ciphers?
No, no, and no — but rigorous results about these topics are certainly game for STOC/FOCS (which have a broader scope than just complexity).
Comment #17 February 18th, 2006 at 5:32 pm
scott 4:59:
i’m just curious because I don’t really understand how I feel about the issue myself.
maybe we should start with something more basic. can we all agree that “logic” (i.e. foundations of math) is pretty boring and flavorless?
sure, we all got that little rush when we heard the story of the “fall of mathematics” in the early 20th century, and we learn about axiomization, set theory, peano arithmetic, the absolvence of absolute mathematical truth, the infinitude of infinities, and so on. and then maybe again with the axiom of choice, continuum hypothesis, independence, forcing, and various incompleteness theorems.
but is logic actually fun to do? on an emotional level, do you achieve understanding, intuition? do logicians have a gut feeling for the difference between large cardinals and super-mega-compact-biodegradable cardinals?
Comment #18 February 18th, 2006 at 6:53 pm
Maybe I am Philistine but I think it would be a lot faster if the God guy skipped his chess lessons and offered us something tangible instead. (Room-temperature superconducting beard would do for me – if He was ready to share a prep procedure how he is growing it.)
Comment #19 February 18th, 2006 at 7:00 pm
I would like him to have created a chess problem he couldn’t solve.
Comment #20 February 18th, 2006 at 7:14 pm
Scott: I think that the question turns on semantics to some extent if you argue that complexity theory began with Hartmanis and Stearns rather than with Turing and von Neumann. But I concede that your semantics are reasonably standard.
Even so, I cannot accept your thesis as the whole truth. Everyone understands that algorithms are important in real life, and not just as beautiful mathematics. You need complexity theory to know when not to look for a fast algorithm. (Not to get into debates over CS education. Whether or not most CS majors need to know, someone needs to know.) A good theory of when there probably (or certainly) is no fast algorithm is also eventually a source of hints for the existence of fast algorithms.
To turn to a professional (if not particularly practical) example, one of our big questions is to find a quantum polynomial-time algorithm for graph isomorphism. Has anyone proved that it is in QMA? Does it make sense to work so hard on whether GI is in BQP if it isn’t even known to be in QMA?
For that matter, the whole field of quantum computation can be viewed as a triumph of complexity theory. Bernstein-Vazirani begat Simon; Simon begat Shor. Bernstein-Vazirani was a complexity theory paper, written to understand more rigorously what Deutsch and Feynman were talking about.
Comment #21 February 18th, 2006 at 8:55 pm
Greg:
Has anyone proved that [graph isomorphism] is in QMA?
No, that’s an open problem. If you throw away the group structure, then graph isomorphism corresponds to the class SZK. I’ve conjectured for a long time that there exists an oracle relative to which SZK is not in QMA (generalizing my collision lower bound, which gave an oracle relative to which SZK is not in BQP). But getting such an oracle is also an open problem.
Comment #22 February 18th, 2006 at 9:09 pm
Everyone understands that algorithms are important in real life, and not just as beautiful mathematics … For that matter, the whole field of quantum computation can be viewed as a triumph of complexity theory.
Greg: For the second time in two posts, I think you’re debating a phantom! š I agree that complexity has an enormous application as the foundation of CS, just as QM has an enormous application as the foundation of lasers, transistors, etc. But if the physicists meekly presented QM as being “about” lasers and transistors, then it would never arouse the level of popular interest that it has. (And I think that interest is entirely justified, even if much of it is squandered on dreck like What the Bleep?)
Comment #23 February 18th, 2006 at 10:50 pm
Scott: For the second time in two posts, I think you’re debating a phantom! š I agree that complexity has an enormous application as the foundation of CS, just as QM has an enormous application as the foundation of lasers, transistors, etc.
No, I’m going to stick to my guns this time :-). You said:
The first lesson is that computational complexity theory is really, really, really not about computers.
But you cannot quite say that computers are to complexity as lasers are to quantum mechanics. Computers are, by design and intent, a full physical model (if also a finite approximation) of the main object of complexity theory. Whereas other practical realizations of QM are not called lasers, any practical realization of complexity theory would also be called a computer.
It would be a bit closer analogy if you said that quantum mechanics is not about atomic structure, it is about abstract principles of which atomic structure is an example. That is not entirely wrong either — witness quantum information theory and operator algebras — but a condensed matter physicist could only respond, “Huh?”
Comment #24 February 18th, 2006 at 11:10 pm
Greg,
At the most fundamental level, the complexity of an object concerns the resources needed to construct that object from a (usually finite) set of “simple objects” using a (usually finite) set of “simple operations.”
E.g. formula complexity using real constants (simple objects), and addition and multiplication symbols (simple operations), where the complexity of a formula is equal (say) to its size.
I don’t see any mention (or need) for a computer here.
Comment #25 February 19th, 2006 at 1:45 am
Anonymous 11:10PM: Yes, you can view complexity theory as a logician instead of as a computer scientist or as some other kind of mathematician. This is a fine point of view, maybe even a philosophically complete one if you have a stoic mindset.
My view is different. I think that studying complexity theory without direct interest in computers is like studying reproductive biology without having sex. Reproductive biology is a fine and noble intellectual pursuit, but it isn’t the real fun.
(Indeed, writing software without studying complexity theory, or at least theory of algorithms, is like having sex without knowing any reproductive biology.)
Comment #26 February 19th, 2006 at 2:29 am
greg,
your “reproductive biology sex” analogy has nothing to do with reproductive biology. In general, doing “activity A without having sex” is “missing the real fun.”
but it’s also really weird. what about people who do mathematical physics without a direct interest in physics? or differential equations without a direct interest in, say, the non-linear schrodinger equation? or problem solvers like bourgain who do everything without a direct interesting in anything?
I do have an interest in computers, but it is rather distinct from my interest in complexity theory. I suspect that many reproductive biologists feel the same way.
Comment #27 February 19th, 2006 at 2:43 am
What about people who do mathematical physics without a direct interest in physics?
I have to wonder about that, to be honest.
Or differential equations without a direct interest in, say, the non-linear schrodinger equation?
Well, that is a strained analogy. There are many reasons to be interested in differential equations.
Or problem solvers like bourgain who do everything without a direct interesting in anything?
I don’t think that that’s quite fair to Bourgain.
Comment #28 February 19th, 2006 at 3:53 am
isn’t the real problem with complexity theory that the resulting mathematics is usually superficial and shallow?
I personally find results such as IP=PSPACE, NP=PCP(log n,1), BPP=P if EXP requires exponential circuits, FACTORING in QBP, PRIMES in P, and undirected connectivity in L to be extremely interesting. I find the questions that we have not yet solved to be even deeper.
Complexity theorists interact more and more with other branches of math (two examples are the connections between zig-zag constructions and semi-direct products, and between extractors and additive number theory). As we go further and further we’ll probably see complexity theorists using more branches of math, and more mathematicians using results that came from complexity theory.
Comment #29 February 19th, 2006 at 5:57 am
This post has been removed by the author.
Comment #30 February 19th, 2006 at 5:58 am
Brilliant stuff, Scott, and terrific comments as well. As a writer and public policy researcher, not a mathematician, I can say with confidence that Cohen’s are the words of a fool. Those in his line of work, I promise, have opportunities to solve for X all the time, if they understand enough about how the world works to realize that the possibility presents itself. He and his readers have suffered for years, obviously unknowingly, from his ignorance.
But if math is to be theology, I also hope that you new theologians won’t complain too bitterly if many in the peonage refuse to accept your proffered faith with a zeal equaling your own.
In the end, to convert the masses, perhaps you must demonstrate not just wizardry but utility – when Christ turned water into wine at a wedding, people at the party could drink it. Even then, somebody had to die before the thing really took off. š
Comment #31 February 19th, 2006 at 8:50 am
gritsforbreakfast: Thanks for the feedback! My perspective is almost exactly the opposite of yours.
To wit: what amazes me about religion is that it attracts so many adherents despite having no obvious application.
(Your water-to-wine example proves the rule, given its obvious difficulties regarding corroboration and repeatability. š )
Conversely, what amazes me about math and science is that they attract so few “adherents,” despite providing the economic foundation of our entire civilization.
To me, this just confirms what should have been obvious to any observer of the last two US elections: that human beings are not even approximately economic agents. If the “spirit” moves them, they’ll choose a recession over blowjobs and a ballooning deficit over gay rights.
My question is: why don’t science popularizers realize that? Why don’t they cut the Mr. Wizard crap, and counter the religious fundamentalists on their own turf — by offering something worthy of awe, reverence, and zeal?
One answer is that the best ones, like Carl Sagan, did.
Comment #32 February 19th, 2006 at 12:33 pm
Old Aristotle divided metaphysics, like Caesar later divide Gaul, into three parts: one part was ontology (the study of existence), one part theology, and one part first science, or metaphysics proper. I see the project of Modern Philosophy, culminating in Kant, as taking out the meaningful parts of theology and placing them under either ontology or metaphysics. Someone like Frank Tipler, in The Physics of Immortality, has a God — but he’s accounted for and known by way of ontological and metaphysical categories (which for him are adequately expressed by scientific truths).
Your “revival” of theology here seems in conflict with your own speculations that P!=NP is a physical principle. It seems like it must be one or the other.
As to questions, I suppose that I would like to know why you think that Lebesque Measure, as opposed to something finitely additive, is THE way that probabilities need to be represented in physical theory. Here in Charlotte, we spend a lot of time on financial (as opposed to civil, or electrical) engineering — I’d like to tell people how to bet in suboptimal situations, and I just can’t give them any advice whatever if the house is against them (but they must bet).
Comment #33 February 19th, 2006 at 7:04 pm
Your “revival” of theology here seems in conflict with your own speculations that P!=NP is a physical principle. It seems like it must be one or the other.
Drew: Your comment reminds me why I didn’t become a philosopher. Stinkin’ consistency with previous things I’ve said!
Seriously: What I’ve advocated as a physical principle is not that P!=NP, but that NP-complete problems are not efficiently solvable using the resources of the physical universe (whatever those are). Were this principle true, it would be a statement about the inability of physical agents to achieve certain “godlike” powers — and therefore a confirmation that those powers are indeed “godlike.”
So I don’t see a need to choose. š
Comment #34 February 20th, 2006 at 12:01 am
Scott:
My question is: why don’t science popularizers realize that? Why don’t they cut the Mr. Wizard crap, and counter the religious fundamentalists on their own turf — by offering something worthy of awe, reverence, and zeal?
It’s very normal that people give less credit (in terms of awe, reverence or zeal) to more obvious (understandable by humans) things. So more often than not religion attracts more adherents. Once people know that some-things are proven and repeatable people don’t need to adhere to that and scientists won’t like to and cannot profess things before they prove them.
I guess the fact that our economic foundations rely on science will take care of attracting people to adhere to science with a sufficient degree.
Comment #35 February 20th, 2006 at 12:07 am
I wanted to comment that the way you gave an example of the power of interaction is really driving and clear.
Comment #36 February 21st, 2006 at 9:19 am
My question is: What is your take on Goedel’s dilemma (either people are not Turing machines but can prove any given true theorem of number theory, or people are Turing machines but there are true theorems of number theory people cannot prove)?
Comment #37 December 8th, 2006 at 6:09 am
[…] The Fable of the Chessmaster suggests that a perfect chess master could demonstrate their mastery to a high degree of certainty without revealing their strategies. Scott goes on to suggest that we can think of complexity theory as “mathematical theology” […]
Comment #38 December 21st, 2006 at 8:02 pm
[…] Shtetl-Optimized « The Fable of the Chessmaster Jewish inferiority complex in brief, unfamiliar remission » […]