The phase transitions in computational problems that have been discovered to date have revealed surprising regularities across many different problems and many different algorithms. Such universal behavior was quite unexpected and has the potential to illuminate the nature of computational problems in fresh and fruitful ways. In particular, the location of the phase transition point might provide a systematic basis for selecting the type of algorithm to use on a given problem. Moreover, having made the analogy between physical phase transitions and computational phase transitions, one is left to wonder whether other phenomena from statistical physics might be manifest in computational systems.

The information exchange need not all be one way however. Whereas the study of physical systems is limited by the laws of physics, in computer science we can posit arbitrarily strong coupling between any variables we please. This motivates the study of phase transition phenomena in higher dimensions than has hitherto been the case and could result in new advances in other fields.

Thu May 16 15:45:43 PDT 1996