Category: Computer Science

[Over at Shtetl-Optimized, Scott Aaronson has decided to take a shot at physicists with his cute little fable The Physicists and the Wagon. Scott specifically called me out, so I feel obliged to respond. Of course I would have liked to respond with a fable directly related to Scott’s main point, but that is damn hard, so instead I present to you a fable which may, or may not bear some relationship with Scott’s post and whose moral is mostly to harp on computer scientists not trusting physicists. If confronted I will immediately deny that I wrote the fable below or that the fable represents anything coming close to my true feelings on the subject.]
Once upon a time and a very good time it was there was a Physicist coming down along the road and this Physicist that was coming down along the road met a nicens little boy named Computer Science. [ed note: bonus points if you recognize this mangled famous opening line.]
Physicist, being ever interested in learning new things, began to have a conversation with the nicens little boy named Computer Science. Computer Scientist, it turns out, he had all of these really fun toys which were all labeled by combinations of letters and numbers (like P and NP and BPP and AC_0.) Physicist was quite confused by all of these letters. What did they mean? Why were there so many? It almost sounded like his friend Old-School Biology to him [ed note: if you’re going to hammer CS, why not hammer other fields equally?]
Computer Science patiently explained to Physicist what all of these strange letter combinations were and the accompaning beasts which they described, but really the physicist only listened to a bit of what he said. He really liked the complexity classes P and BPP, and understood the deep dark hatred everyone should have for complexity classes like NP-complete or NEXP. He was a bit confused by PSPACE and wondered, in a bout of extraillusionary intelligence, whether he should tell Computer Science about Special Relativity. But he really didn’t understand Computer Scientist’s obsession with the endless array of complexity classes.
After blabbering on for quite a while, Computer Scientist noticed that Physicst was nodding off. “Why aren’t you paying attention, Mr. Physicist?”
“Well, you keep talking about this endless array of complexity classes, and while it all sounds quite fascinating, I’m wondering if you could get to the point?”
Computer Scientist then launched into a diatribe about “proving” all sorts of different things (which the computer scientist insisted on refering to as “theorems.” This made these things seem big and important, and secure, like how he felt when he was safe in his fenced suburban home.) Physicist couldn’t take much of this diatribe, so he interupted, “But if you really feel strongly that these complexity classes are different, but you can’t prove it, why don’t you just accept it and move on? I mean you’ve got ample experience telling you that P does not equal NP, right?”
At this point Computer Scientist’s head bulged, his veins began to stand out from his neck, and he emmitted a long loud shriek which sounded a lot like fingernails being dragged across a chalkboard…and the nails breaking. Computer Scientist, however, had long mastered the art of immediate Zen meditation, and so began chanting to himself and calmed himself down by dumping the core of his memory and then rebooting.
“But, Physicist, if you can’t prove something, then how do you know it is true? Won’t you spend all of your life worrying about whether it is true or not?”
“Let me tell you a story” said Physicist, and therein he launched into a little sub-fable of his own:

Once upon a time, there was a clan known as the statistical physicists. These statistical physicists studied all kinds of interesting physical systems, their distinction being that they were very good with large numbers of interacting systems. They were particularly good at describing systems which changed their appearance (which physicists like to call “their phase”.) In other words they were particularly good at describing phase transitions.
Now some of members of the clan of computer scientists were smart enough to learn a little about the theory of phase transitions. Some of these members of the computer science clan, like almost every rational being, were particularly enamored with computational problems which were NP-complete. When they investigated these problems, together with members of the statitical physics clan, they discovered that instances of these NP-complete problems came in different phases and that, just like the phases they studied in physics, they could study the phase transitions between these different instances of the problem. Now this was fun! And so, because this worked for a few instances of the different NP-complete problems, these crazy scientists conjectured that NP-complete problems were distinguished from other computational problems by the existence of different phases and a phase transition. Indeed they were even bolder and claimed that the hard problems, the ones for which no known polynomial time algorithm would suceed, were those problems near this phase transition.
Of course this was in some ways both profound and silly. Silly because the scientist could not prove that this was true. Profound because the scienists had discovered that a property of physical systems could be mapped to a computational problem in an interesting, and possibly fruitful manner.
But scientists are a skeptical group. So no conjecture will last long without being challenged. So one scientist did. He examined the integer partitioning problem. The integer partitioning problem is, given a set of of k integers between 1 and N decide whether there is a subset of these k integers whose sum is equal to the sum of the elements not in this subset. This problem is a beast of the NP-complete kind. So according to what others were boldly conjecturing, this problem should have had a phase transtion. But, this scientist claimed, in an article entitled “The Use and Abuse of Statistical Mechanics in Computational Complexity,” that this problem did not exibit a phase transition. It was thus claimed to be a counter example to the bold conjecture!
But not everyone was sold on this conterargument. Indeed, numerical results immediately began to dispute this counterargument. And then a memeber of the statistical physics crowd, Stephan Mertens, approached the problem like a physicist. He showed how to approach the number partitioning problem like a problem in statistical mechanics. He then showed that there was a phase transition in this problem and explained how the effects of working with finite numbers of numbers effected the properties of this transition. Now, Mertens approached this problem with all the tools and lore of statistical physics. These tools involved many things that physicists were confortable with, including, methods which physicists love known as approximations.
So it might seem that the story would end here. Mertens had shown that there was a phase transition in the problem, identified where and how this phase transition occured, and triumphantly explained scaling effects near where the phase transition occured. But, no! Why? Well because while Merten had “shown” these results, he had done so using a approximations which physicists were confortable with, but which were not “proven!”
So physicists reading about this would probably have been happy. But not so, for those who work in the clan of computer science! There the approximation was considered an abomination, something so disgusting and foul that it should be banished to the far ends of the earth (no one apparently having told the computer science clan that the world was not flat 😉 )
Thus a brave group of computer scientists/mathematicians/mathematical physicists decided to see if what these crazy physicists were saying with their abominable approximation was true. And by true, they meant provably true. So Borgs, Chayes and Pittel (the brave group), in a beautiful forty page paper, investigated and proved results about the phase transition in the integer partitioning problem. And what did they discover? They discovered, to their surprise, that Merten’s results, even using his abominable approximation, were correct! While he had made an abominable approximation, Merten’s result agreed with the exact result (in appropriate infinite instance size limits.) Those damn physicists had invoked an unproven and abominable approximation and still gotten the right answer! (As a side note the work of BCP also pens down the finite size effects in a rigorous manner.)

“Wake up Computer Scientist!”
“Oh, I’ve been awake. I just like to rest my eyes when I’m listening to stories. It helps me visualize the characters involved. For the physicists I was imagining a moocow.” [ed note: this joke only makes sense if you know where the first line of this post comes from. This is an example of a obsoke: a joke so obscure that prehaps only the author of the joke understands why it is funny.]
“So what do you think about my story?”
“I think that sometimes, even people like you Physicist, can do produce profound results even though you can’t prove why they work. It also seems that you don’t care so much if something is proven as much as if it agrees with your experience. I could never live that way, of course. It seems, so, so…uncertain!”
“Which reminds me, Computer Scientist, have you ever heard of this thing called quantum mechanics?”
“No, what is that? Some kind of car repair shop?”
“Heh. Let’s go to the pub and get some beer and then, boy do I have a story for you….”