Mathematical Digest

Short Summaries of Articles about Mathematics
in the Popular Press

"Can't Get No Satisfaction," by Brian Hayes. American Scientist,March/April 1997, pages 108-112.

The investigation of the class of problems known as NP constitutes one of themajor challenges in theoretical computer science. Problems are said to be inthe class NP if no efficient algorithm (where efficiency is measured in aspecific way) is known to exist. This article looks at a specific problem,known as the satisfiability problem, to uncover an intriguing aspect of NP. Itturns out that the satisfiability problem undergoes a phase transition from"easy to solve" to "hard to solve" back to "easy to solve," as a certainparameter is varied. This phenomenon, which is found in other problems in NPas well, bears a striking resemblance to phase transitions in physical systems,such as the transition from liquid to solid.