I’ve been meaning to ask this question for a long time, and Indistinguishable’s thread on the supposed proof of P/=NP reminded me. I’ve read several bits on SAT where the subject of phase transitions have come up. From what I gather, there appears to be some hint that these are closely related to the phase transitions one often sees in physics, yet nothing I have read seems to spell this out explicitly (it’s always kind of “nudge-nudge, wink-wink”). What is the latest thinking on the connection between these differing instances of phase transition? Do phase transitions in physics tell us anything useful about phase transitions in SAT (or vice-versa).
Just so folks don’t have the same confusion I had initially: you’re talking about the Boolean satisfiability problem, not the Scholastic Assessment Test, right?
If a statistical system has some macroscopic property that changes abruptly from the neighborhood of one value to the neighborhood of another when a parameter governing the system is varied across a critical value, then that system has a phase transition.
Changes in physical states of matter are the most familiar examples of phase transitions: many physical properties change abruptly as the temperature crosses, say, the freezing point of a material. Traffic is another example: as automobile density increases past a critical point, traffic jams will appear. Phase transitions are a nearly universal feature of statistical systems that have even the most basic microscopic dynamics.
The SAT problem is just another such example. This paper I got Googling “phase transition SAT” has a relevant diagram. The ensemble average satisfiability of problems switches abruptly from 100% to 0% as the ratio of clauses to variables increases across a threshold.
Knowing that the problem has a phase transition is important in algorithm design, as how you approach things on one side of the threshold may be very different from how you approach things on the other. Also, calculating things like computational complexity are aided by knowing a transition occurs. However, the simple fact that phase transitions exist in physical systems, too, is (I would think) not particularly useful in any practical sense. Handy mathematical approaches have been developed thanks to the study of physical systems, so that’s sort of a connection. But, I don’t think anyone is saying things like: a ferromagnetic material passing through its Curie temperature does X so we can show that this SAT problem does Y.
I’m aware that techniques from statistical physics have been used to find algorithms that can solve SAT-instances with millions of variables faster than any other known algorithm. This is kind of a superficial connection.
However, I was under the distinct impression that some computer scientists think there’s something about where phase transitions occur, or some other aspect, that links them to certain physical systems at a much more fundamental level than merely being instances of the same phenomenon. I’m pretty sure I’ve read some writing of Scott Aaronson to this effect, yet now I can’t find the paper I’m thinking about. Grr.
Perhaps I’m mistaken, or have gotten the wrong impression. Digging around for “Scott Aaronson” and “phase transition” lead me to this comment on his site:
Which I guess is just talking about the superficial connection mentioned earlier.
I’m drawing not on any particular knowledge of SAT (I’d not heard of it until this morning) but on having seen many other not-really-physics systems with phase transitions whose experts love to point out “Hey, look! A phase transition!” In every case, the paragraphs read just like these SAT-related ones, namely:
(1) “We’ve got a transition. Cool.”
(2) “These are just like the ones in physics, on a very deep level [li].”/li “We can use existing statistical tools.”
[li] and “a very deep level”, in turn, always turns out to be referring to the connection you call superficial. I personally much prefer your terminology. 
I hypothesize that the apparent excitement stems from the field’s not being generally familiar with phase transitions.[/li]
But, I suppose fundamentally my post is just a WAG. However, I’d be surprised if there was something “very deep” going on.