|
 |
"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 the major challenges in theoretical computer science. Problems are said to be in the class NP if no efficient algorithm (where efficiency is measured in a specific way) is known to exist. This article looks at a specific problem, known as the satisfiability problem, to uncover an intriguing aspect of NP. It turns out that the satisfiability problem undergoes a phase transition from "easy to solve" to "hard to solve" back to "easy to solve," as a certain parameter is varied. This phenomenon, which is found in other problems in NP as well, bears a striking resemblance to phase transitions in physical systems, such as the transition from liquid to solid.
