[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….”
Hey there Baby Tucktoo. Ever hear that Car Talk clip where Ray tells some woman that she needs a quantum mechanic for her little H-4 Turbo? Outstanding…
Physicist replied, “Boy, one beer and you become a real wise guy, huh? At least you aren’t like that other fella who got in a fistfight with me over P=NP after one beer. If you’re looking for someone who works out what can be constructed with physical theories, let me introduce you to my friend. I have to fill in for her some times when she hasn’t learned the theories yet, but once she understands the theories, she’s a whiz. Computer Science, meet Engineer.”
JM wins the prize! The prize? Three quarks!
At the pub, Computer Scientist ordered beers for two.
“Hey, I was just ribbin’ ya,” he said to Physicist. “Not only do I know quantum mechanics, but my knowledge of it is pure and information-theoretic — unencumbered by weird distractions like infinite-dimensional Hilbert spaces, boson/fermion statistics, etc. etc. (Incidentally, fermions are the ones with the minus signs.)”
“I know,” said Physicist. “But about them phase transitions … a pretty clear triumph for nonrigorous approximations, huh?”
“Yes,” replied Computer Scientist. “That’s why I bought you a beer.”
Physicist stood up, pumped his fists, and started belting out “We Are The Champions” for all the pub to hear.
“Dude,” interrupted Computer Scientist. “You wouldn’t know it was a triumph if those conjectures hadn’t later been rigorously proved!”
“But who cares?” said Physicist, sitting down. “The point is, we were right! So why shouldn’t we be right about complexity classes? If our intuition was correct about phase transitions, then by physicist-induction, it must be correct about everything else as well.”
“Would your intuition have told you that IP=PSPACE, or that maximum matching is in P, or that matrix multiplication is in o(n^2.376), or that factoring is in BQP?”
Physicist pondered this for a minute while downing his beer. Finally he said: “There seems to be a difference between these questions and the phase transition questions.”
“Yes,” said Computer Scientist. “One type of question involves estimating a random variable, like the number of solutions to a partitioning problem. The other type of question is existential. It asks whether there’s any way to do something — possibly a way unlike anything that’s ever been thought of. My conjecture is this: physicist-intuition will generally work for the first type of question. But for the second type of question, it will often lead to the mistaken prediction that there’s no way to do something, just because there’s no obvious way.”
“That’s an interesting conjecture!” said Physicist. “Do you have any evidence for it?”
“No,” Computer Scientist admitted. “But my intuition tells me it’s true.”
Feynman:
“We know a lot more than we can prove”
“Mathematics is to physics as masturbation is to sex”
See
http://infoproc.blogspot.com/2006/06/proof.html
They call it sex, but until they prove something it’s really just foreplay.
bilingual dictionary
P=physics M=math
PROOF (P)a few examples (M)an exercise in second order logic
INEQUALITY (P)an approximation; a dull fact, impossible to tell where it came from (M) look at Hardy et al book; apotheosis is Schwartz inequality
NON-CONSTRUCTIVE EXISTENCE PROOF (P)no word available (M)
CONSTRUCTION (P)the only possible kind of existence proof(M) a special type of existence proof, not too sexy
INTUITION (P) the best part of the paper (M)deep secret, do not reveal in your paper
REFERENCES (M)an honest list of all previous work(P)a list of your friends and people who could advance your career
Thanks Dave!! Three quarks. May I have them one at a time, please? 🙂
Great chuckle!
Michel Talagrand’s page has some fun sniping about statistical physics: http://www.math.ohio-state.edu/~talagran/spinglasses/
Sample: …The main tool is the cavity method, that is, induction over the number N of coordinates. Probably it would have been better to coin another name, because what a mathematician means by cavity method is very different from what a physicist means.
This post, and Scott’s orginal post, are possibly the two best posts I’ve ever seen on a QI blog.
JM, no I’m affraid that by the rules I’m confined to giving you the quarks two or three at a time (although there is talk of a combination of five quarks.)
Is it time to abstract these fables from people to problems?
So, 2D-Ising-Magnet walks into a Waterloo bar. “Brrr, it’s freezing out. All my spins are pointing down.” Computer Scientist looks up from the curling match he was watching on TV, “You’re not kidding, my friend! Come, grab a brewdog and grab a seat by the fire, eh.”
One minute later, 3D-Ising-Magnet walks in. “Wow, I can’t remember the last time it was this cold. All my spins are pointing down.” Computer Scientist responds, “Yeah, whatever you say, buddy.”
The serious issue in this monumental “clashes of the Blogs” is perhaps:
Can statistical physics shed light on the NP versus P problem?
Here are some comments about it.
A. What is it about:
1. Decision problems
Here are some decision problems, questions in which you or your computer are given some information and based on it have to answer YES or NO:
1. (Ice-cream)
There are 2N individuals divided into couples and you are told for each person if he likes ice-cream or not. Is it the case that for every couple precisely one of the individuals likes ice-cream?
2. (Parity)
Like problem number one, but this time you ask if altogether there are an even number of individuals that like ice-cream.
2′. (majority) Like above but the question is: are there more people that like ice-creams than people that do not.
3. (Connectivity, percolation)
You have a list of cities and roads between some pairs of them can you walk from city A to city B along the roads?
4. (Matching)
You have N men and N women and a list of pairs that knows each other. Can you have a perfect matching of the men and the women?
5. (Traveling)
You have a list of N cities and roads between some pairs of them can you walk starting from one city along the roads and visit each city precisely once?
Problems 1-4 are in P, namely there is an algorithm that solves them in a polynomial number (in the parameter N) of steps. There are simple computation models which allow to solve efficiently problem 1 but not 2 and above. Problem 3 is “harder” than 2 and 2′ and problem 4 is “harder” than 3 (matching is the first place you need to “backtrack” in your algorithm) but these statements already reflect very difficult questions in computational complexity.
2. P versus NP
The conjecture that P is not NP is can be stated as follows: There is no polynomial-time algorithm for problem number 5.
(The conjecture that for problem number 5 you need something like exhaustive search which takes exponential number of steps, was around even before the precise formulation of the P vs. NP problem. a major new insight was the notion of NP. It has to do with the fact that if the answer is YES, there is a proof for this fact that requires a polynomial number of steps.)
The conjecture that P is not equal NP is a mathematical question and therefore called for a mathematical proof. And the main reason we want to see a proof is that we are very curious if P is equal or is not equal to NP. Of course, any evidence or related discovery, such as heuristic arguments based on some methods of physics, or some conjectural plans for a proof, or proofs of weaker results in this direction etc. are welcomed.
B. Statistical Physics and P versus NP
1. what is the plan?
There is a substantial amount of work relating computational problems with statistical physics. Perhaps the bolder interpretation of this endeavor is as an attempt to shed a new light on the P versus NP problem. Here is how I see this “plan”. I may well be wrong so I will be happy to see a better (English) explanation.
a. Consider a random instance of the problem.
So instead of a Hamiltonian cycle in a graph consider a Hamiltonian cycle in a random graph. Or a random 3-SAT problem.
Of course, this is a very appealing and familiar idea from the point of view of computational complexity and combinatorics. A word of warning is that showing unfeasibility for a random instance may well be much harder than “just” proving that P is not equal to NP. Anyway, this is related to various notions that were studied a lot in computational complexity.
b. Consider a one-parameter family of random problems.
Here is another ingredients of the physics approach. For various problems (both decision problems and optimization problems) statistical physics offers a one parameter class of perturbation depending on “temperature” (say). In combinatorics we are used to random graphs say with various edge-probabilities but statistical physics offers new types of generalization which are certainly interesting.
c. Look at the threshold behavior and at the threshold values.
It is natural from the point of view of statistical physics to look at “threshold points” and to conjecture that the problem is computationally hard precisely when in the random model the probability to have the property is well between 0 and 1. This makes perfect sense, although, as I said, it looks that proving unfeasibility in this case would be harder than showing that P is not NP.
So far, so good, but now come two steps that I feel uncomfortable with.
d. The type of the threshold transition is related to the hardness of computation.
Here comes a conjecture:
(X) “The computational complexity of the problem corresponds to the type of phase transition: First order transition corresponds to P and second order transition correspond to NP.
I do not believe this conjecture even on a heuristic level because I do not believe that the difference between NP-hard problems and problems in P can be manifested by such a simple property. (It still may be of interest to pursue this idea further.)
(For very low complexity classes, AC_0 there is something correct in the direction of this conjecture. This is related to separating problem 1 from 2′ in the list above. It would be nice to be able to separate 1 and 2′ from 3 and 1-3 from 4, before trying to attack 5.)
e. ???
And now comes the second part of the plan that I am not sure about: Let’s suppose that conjecture (X) or some variation is correct. How is it related (precisely or vaguely) to the P versus NP problem?
2. A prototype of a non-convincing usage of statistical physics
Here is a type of arguments (you see around) for why P is not NP that I do not find appealing.
1) consider 3-SAT (fine)
2) Here is a heuristic to solve 3-SAT (ok)
3) Here is a proof based on statistical physics arguments that this heuristic takes exponential number of steps.
4) therefore, we have given evidence that P is not NP.
The problem with such a plan is NOT that the physics proof is not mathematically precise but that the overall logic is not sound.
3. Convincing examples
There is some great stuff about heuristic algorithms based on statistical physics for random 3-SAT and one of the beautiful outcomes
is a heuristic computation of rather precise threshold position
for random SAT problems, that was followed by a mathematical precise proof.
Mertens result that Dave mentions is very impressive. And while it is not surprising that
the “physics” result are confirmed and not refuted by mathematical proofs, it is certainly an achievement to be able to do it. Still there is the question of the relevance and
interpretation from the point of view of complexity.
Overall (with a few exceptions), mathematics tend to slowly confirm “proofs” based on “approximations physicists used” for the mathematical models physicist build. Much of the mathematical endeavor is devoted to understand precisely certain proofs and predictions from physics and to justify what Dave called “approximations physicists use”, and much less attention is devoted to study under which condition the “physics approximations” breaks down. Of course, such “mathematical stamp of approval” is not related to the relevance of these mathematical models for physics itself.
4. Personal conclusion
Overall, the relation between statistical physics and mathematics is very close and in this area ideas and notions related to computations and complexity already play a role and more connections are welcomed. (I expect the direction from computation (but rather “low level” notions) to statistical physics and related probability to be especially fruitful.)
I thing the statistical physics gives a nice new prospective to questions from computational complexity but I am not aware of very useful insights for computational complexity at this time. (I will be happy to learn, though.) Of course, these new problems may be quite exciting from the point of view of statistical physics and related mathematics regardless of their complexity origins.
The problem of P versus NP looks well well beyond the horizon and the specific suggestions from statistical physics related to NP-completeness looks rather unconvincing. (But they can lead to nice stuff.) The NP versus P problem is well beyond the horizon of main-stream computational complexity but there we do witness tremendous new results and insights with clear computational complexity relevance.
Anyway, my very short answer to the question in the title is “I dont know”.
C. This is precisely what they are doing
Dave : “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?”
Here is a story.
There is a place called Oberwolfach which host a large number of mathematical conferences every year. From Offenburg you go to a small town Hausach and from there to an even smaller town Wolfach and from there to a little place called Oberwolfach-Kirche and further to a tiny place Oberwolfach-Walke and then it is a few minutes to the mathematical institute.
There is a little, extremely regional, train from Hausach to Wolfach. (Like the dinky-train from Princeton Junction to Princeton”.)
One day, I was told, a couple of minutes after leaving the station at Hausach the train went off the trucks and to the horror of the seven passengers went down the valleys, up the mountains, crossed the little rivers, and finally went back on truck and entered the Wolfach station. The shattered passengers went shouting to the driver and demanded an explanation. “Let me explain”, he said, “close to Hausach there was this guy, standing on the tracks. I tried to signal him and to warn him to get off but all in vein, what could I do?”
The seven passengers shouted ” you should have run him over!”
“Yes” cried the driver, “this is precisely what I was doing, but this guy ran to the valleys and then to the mou ntains …”
In our case, only a handful of theoretical CS people try to attack directly the P versus NP and indeed the community moves on, assuming that P is not equal NP.
Man everyone trying to get serious on these posts 😉 (Just kidding of course! Sometimes even I can be serious. Not on Saturdays and Sundays, though.)
The point of my using the statistical physics results was not to say anything about the applicability of these results to the P versus NP problem but just to point out that sometimes trusting “approximating” physicists is not as crazy as it sounds. While we may play loose with the words, we don’t really _mean_ to offend our mathematical and computer science friends!
I also agree, partially, with what both you and Scott have basically said which is that it is unlikely that the methods physicists have developed will be useful for proving existential-ish results (particularly those like separating or uniting complexity classes.) But I also don’t see this as a closed case. Physicists have been known to deal with existential results just fine: witness Bell’s inequality, for example, or even, in some sense Goldstone’s theorem. And I am inclined to believe that the connections between physics and computer science complexity are a fruitful ground for bringning a new perspective to computer science. But that’s just my own personal bias showing!
Physicists have been known to deal with existential results just fine: witness Bell’s inequality, for example
Yes, Bell’s inequality was one of the crowning achievements of Honorary Computer Science. No wonder so many “real” physicists have misunderstood or ignored it. 🙂
I’ll bet you more computer scientists than physicists misunderstand Bell’s inequality. 🙂 Of course I’m guessing your definition of computer scientist does not include a lot of people I consider computer scientists! And, of course, I’ll guarantee you that more physicist than computer scientists misunderstand what NP is!
Dave,
Not only that it is not considered as “crazy” to trust approximations coming from physics but rather it is usually considered as quite safe.
What is difficult for a layman to grasp (so if you are in a serious mood you can try to explain sometime), is this:
a) When you have a statistical physics model like the 2-D Ising model or the 3-D model. What precisely do you mean by “solving the model”.
b) What is the significance/interpertation to physics of such a solution.
Having insight on these issues maybe we can try to see how it extends to statistical physics models coming from computation theory and their analysis. For example, what can be the significance for the theory of computing of Merten’s result that you mentioned in the post.
Ian Stewart, in Letters to a Young Mathematician, tells the following tale:
A mathematician at a famous university went to look around the new auditorium, when she got there, she found the dean of the faculty staring at the cieling and muttering to himself, “… forty-five, forty-six, forty-seven …” Naturally she interrupted the count to find out what it was for. “I’m counting the lights,” said the dean. The mathematician looked up at the perfect rectangular array of lights and said, “That’s easy, there are … twelve that way, and … eight that way. Twelve eights are ninety-six.” “No, No,” said the dean impatiently. “I want the *exact* number.”
Gil Kalai said
“For example, what can be the significance for the theory of computing of Merten’s result that you mentioned in the post.”
Listen to the force, Gil…
You pose this as a dark mystery, and well it might be for a mathematician bogged down by the minutae of finding ironclad proofs for everything. But a physicist is not slowed down by such micromanagement. Physicists are the scouts sent out to reconnoiter the territory well ahead of the mathematicians. That’s why physicists often discover the most important principles long before the mathematicians. In Merten’s case, he realized that phase transitions and renormalization group are relevant to Complexity Theory. With hindsight, most physicists will say, OF COURSE. Why? Because Complexity Theory and Renormalization Group both deal with scaling. Even dimensional analysis in engineering deals with scaling. And guess what, they are all related. (Interestingly, Perelman’s proof of Poincare’s Conjecture is also based on scaling ideas from Physics.)
R.R. Tucci
Rrtucci: Let’s consider some of the accomplishments of mathematicians that were already invented when physicists needed them: Lagrangian mechanics, Hamiltonian mechanics, matrices, group representation theory, Riemannian geometry. (For that matter, the “group” in renormalization group was invented by mathematicians for purely mathematical reasons.)
I think that the ability of physicists to make useful approximations is wonderful, and it’s an ability I’ve tried to develop myself. There are multiple ways to come to understanding: intuition, rigorous proof, heuristic argument. They’re all useful. That’s why sometimes mathematicians help the progress of physics, and sometimes physicists help the progress of mathematics.
First: Hey Dave, it’s usually considered ‘gauche’ to make fun of one’s employer – you are in the Computer Science Department, after all.
Second: Here’s a ‘joke’ that Scott’s original little tale reminded me of (cross-posted on his blog in a minute or two). I got this out of a great little novel about a kid with Asperger’s syndrome called The Curious Incident of the Dog in the Night-time by Mark Haddon (that’s the book not the kid). Anyway, here’s the ‘joke,’ best quoted with an additional line from the book:
“There are three men on a train. One of them is an economist and one of them is a logician and one of the is a mathematician. And they have just crossed the border into Scotland (I don’t know why they are going to Scotland) and they see a brown cow standing in a field from the window of the train (and the cow is standing parallel to the train).
And the economist says, ‘Look, the cows in Scotland are brown.’
And the logician says, ‘No. There are cows in Scotland of which one at least is brown.’
And the mathematician says, ‘No. There is at least on cow in Scotland, of which one side appears to be brown.’
And it is funny because economists are not real scientists, and because logicians think more clearly, but mathematicians are best.”
Ah, a pun about a joke – something my father would, well, udder. On the other hand, cows are pretty funny in general (or people near cows – my father used to stop the car whenever we were near a field of cows and moo very convincingly at them – I stopped being embarassed by this when I had my own kids).
Speaking of cows, I took my kids to see the new movie Cars (which I actually enjoyed despite some of the reviews) and the ‘cows’ were tractors (the ‘bull’ was a harvester) complete with parts underneath resembling udders. I, too, grew up in the country (or on the edge of it, anyway, though my grandmother did own a farm) and still live – well, on the edge of it at least – and so I have a great liking for all things ‘cow.’
Ah, but that is all horribly off-topic. I did miss your disclaimer (and will sheepishly admit to skimming portions of your parable as my attention span is short at times, particularly after a day of appliance shopping [12-yr.-old fridge is dying]).
Hey Ian, you’ll note my disclamer at the begining of the post! I find myself loving both computer science and physics. But Scott likes to pretend I’m more physicist than computer scientist. At least for the sake of the argument. I have a rougher time with the mathematicians. I mean I grew up in the country and have never seen a cow with one brown side 🙂
On a similar note, I know a ton of cow jokes. Most of them are udder disasters.
Ian, it seems we shared fathers who would moo at the cows! Moocows!
Walt said: I think that the ability of physicists to make useful approximations is wonderful, and it’s an ability I’ve tried to develop myself. There are multiple ways to come to understanding: intuition, rigorous proof, heuristic argument. They’re all useful. That’s why sometimes mathematicians help the progress of physics, and sometimes physicists help the progress of mathematics.
This sounds a great way to put it! I’d add to Wald’s list of “ingredients for understanding” also: discussions, debates, interaction, some backtracking, a bit of skepticism, vague ideas, crazy models and sharp turns, (and even jokes).
RR Tucci said: In Merten’s case, he realized that phase transitions and renormalization group are relevant to Complexity Theory. With hindsight, most physicists will say, OF COURSE. Why? Because Complexity Theory and Renormalization Group both deal with scaling.
This sounds interesting and appealing. More details are most welcomed. Phase transition and scaling are truly wonderful. Insights for computation complexity theory along this line are still in the category of “vague ideas” but this is fine, press on!
OK, Dave, for those of us who are either oblivious or just plain thick, what was that opening line a reference to anyway?
(Oh, and my dad was scarily good at the mooing – the cows used to wander over to him and moo back.)
“This sounds interesting and appealing. More details are most welcomed. Phase transition and scaling are truly wonderful.”
I don’t work on complexity theory so I’m not familiar with the complexity theory literature on this subject. But I am very familiar with Renormalization Group. You can get a gentle introduction and some references to the connection of RG to scaling of differential equations near a singularity in the following textbook “Lectures on Phase Transitions and the Renormalization Group” by Nigel Goldenfeld
Ian,
As google suggests, it’s a typo. It should be tuckoo.
Ian, it’s the opening page or so of a novel by James Joyce called `Portrait of the Artist as a Young Man’. It’s a semi-autobiography.
A nice introfuction to the connection between statistical physics and computational complexity is “Introduction: where statistical physics meets computation” by Allon Percus, Gabriel Istrate and Chris Moore. (This is an introduction to a book “Computational Complexity and Statistical Physics” edited by these authors.)
Well, despite my lack of recognition at the James Joyce reference, I am well-read in literature – just not Joyce. I suppose, someday, it will cross my radar. Thanks for the heads-up, Joe.
I couldn’t avoid him. Not only did we have to cover Portrait of the Artist for our state exams (the Irish Leaving Certificate) when I was 17, but my secondary school (Belvedere College) featured heavily in the latter half of the book. It also led to the name of my blog.
Mathematicians, Cows, and William Tutte,
1. A joke about mathematicians
Here is a better joke about mathematicians:
A rich person wanted to have a perfect racing horse and he decided to approach this matter scientifically: So he asked a biologist a veterinary a horse-trainer and a mathematician to give him the formula for a perfect racing- horse.
The biologist explained which blend of horses he should cross.
The veterinary explained how to feed them and prevent illness.
The trainer explained how precisely the horse should be trained from very young age and how it should be prepared for races.
He did not hear from the mathematician.
A few days later he met the mathematician with eyes red from nights without sleep.
“Well, do you have an answer for me,” the rich asked.
“This is a tough one” said the mathematician, then paused and continued
“… but I did solve an important special case: The case of spherical horses.”
Commentary: This joke belongs to the nice genre of jokes about how to build a perfect racing horses.
The most hilarious one that I know is about the
horse that could do this (The concept of a horse that can do this is already very funny but the full joke is really great even beyond just the funny fact that the horse can do this . )
2. Jokes about cows that mathematicians tend to like
A guy went to his friend on the farm and the friend showed him two cows: a
black cow and a white cow
“The black cow is great”, said the farmer “it gives me 500 gallons of milk every day”
“wow”, said the friend, “and what about the white cow?”
“also” replied the farmer
“The black cow literally cost me nothing” continued the farmer “she does not need any food”
“wow” said the friend “and what about the white cow?”
“also” replied the farmer
“The black cow was not sick for a single day in her entire life” continued the farmer
“wow” said the friend “and what about the white cow?”
“also” replied the farmer
The friend was puzzled: “But why do you tell me all this wonderful things about the black cow when apparently the white cow is just as wonderful?”
“Ohh this is simple” said the farmer “the black cow is mine!”
“and what about the white cow?” asked the friend
“also” said the farmer
and if you want there is a moral to this story.
commentary: This is an interactive joke and it is a matter of debate if the interactive part at the end add to it, complexity theory teaches us that interactive proofs are more powerful than ordinary proofs so it comes to reason that interactive jokes are also more powerful than ordinary joke, Scott? also, if you want the black cow symbolize quantum fault tolerance and the white cow classic fault tolerance, but if you don’t want? …
3. William Tutte
And finally here is a also nice story about the mathematician William Tutte.
(A lot of “quantum gravity” is based on his work on enumerating planar maps that he studied in trying to prove the four color conjecture.)
Tutte studied in Cambridge and his supervisor, Shaun Wylie, gave him some mathematical conjecture to work on.
Wylie did not hear from Tutte until nine months later when he saw Tutte in the corridor.
“William, did you prove the conjecture I gave you?” he asked.
“No” replied Tutte, and walked away
But than Wylie recalled what a shy person Tutte was,
so he shouted to Tutte who was already at the other end of the corridor:
“William, did you find a counter example?”
“Yes” replied Tutte.
Racing horses, moral links and Stanislaw Ulam.
The perfect horse-race race: Enter physicist
… Then the rich person who wanted a perfect racing-horse decided to consult a physicist. “I got it covered” said the physicist. “Don’t waste your money on the biologist and the vet. and the trainer and, of course, not on the mathematician. You can let them all go. Build me these multi-billion dollars colliders and I will give you a
perfect horse – a quantum horse. It is more powerful than anything you ever saw and it only eats anyons! ”
Challenge: try something for a computer scientist.
Also
The link for the moral in the black/white cow jokes did not go through.
Let’s try again:
…
The friend was puzzled: “But why do you tell me all this wonderful things about the black cow when apparently the white cow is just as wonderful?”
“Ohh this is simple” said the farmer “the black cow is mine!”
“I see,” said the friend, “and what about the white cow?”
“also” said the farmer
and if you want there is
a
moral to this story.
Ulam and the “future of mathematics”
At some time Ulam was scheduled to give a talk in the University of Chicago titled “The future of mathematics”
Stanislaw Ulam was a rather famous mathematician and a major player in building the H-bomb, (which shows you that, contrary to the impression you may get from this post and comments, when a truly noble task comes along – mathematicians and physicists can work in harmony shoulder to shoulder!) so a large audience gathered.
Ulam had a trousers with two suspenders ending at a single front button. At some time along the talk when Ulam got excited this single button collapsed, the suspenders got untied and the trousers went slowly down revealing a colorful boxer underwear. Ulam did not notice it for a couple of minutes and then when he did, he raised the trousers and just supported them with his hand, which was ok except that at times when he got over-excited and waved both hand the trousers went down again.
Beside the colorful boxer under-pants, Ulam’s lecture was a completely mundane mathematical talk: problems, lemmas, theorems, conjectures, little proofs, nothing unusual, and not a word about the future of mathematics.
At the questions part, a person from the audience asked Ulam about the future of mathematics. Ulam looked at him rather surprised, and replied very slowly.
“Young man” Ulam said, “you must understand: we are now in the present, and the future only comes later , so it is not possible to know what will be for mathematics in the future, simply because it did not happen yet.”
Then other people asked similar questions and reminded Ulam that the title of the talk was “the future of mathematics” but Ulam insisted that these questions are misguided since the future will only come at a later time. At the very end he was ready to say that he expects unexpected connections between PDE and the theory of large cardinals.
CS scientists, be patient. Physicists in QI are working hard to solve your NP problems, so you can have a day of sleep:p
Following the discussions here I read Stephan Mertens’ (lovely) paper in the Percus et als. book mentioned above and went through a few other papers. I do think now that the results coming from statistical physics give interesting insights for average case computation complexity, and the different behavior below, above, and at the phase transition are interesting, somewhat surprising, and also resembles some phenomena found in “ordinary” computational complexity. Also, some algorithms in this context that come (God-knows-how) from physics intuition are quite remarkable. (In the tradition of Monte-Carlo method, Metropolis algorithm and simulated annealing.)
Dave wrote: “These crazy scientists conjectured that NP-complete problems were distinguished from other computational problems by the existence of different phases and a phase transition.”
As for the more ambitious conjecture metioned by Dave about the relation to NP-completeness,
I am still rather not-optimistic (or “open-minded optimist” rephrasing G. W. Bush). Yet, having very ambitious conjectures on the table can be useful and fun, … unless, it is regarded politically incorrect to doubt them. I still suggest to examine this conjecture by gradually climbing up the computational complexity ladder, e.g., throuh problems 1-5 that I mentioned. (Adding, perhaps, the AND-OR tree as problem 2.5 between 2,2′ and 3.)
Who or WTF is a nicens?
“Nicens” is a word in James Joyce’s novel “Portrait of an Artist as a Young Man”
I’m starting to notice physicists seem more black and white than quantun physicists and with black and white can only go so far in finding the truth about any physics.