"On the Threshold," by Brian Hayes. American Scientist, January-February 2003, pages 12-17.
The threshold is the boundary between solvable and unsolvable problems. Hayes devotes most of the article to the problem of graph-coloring with three colors: That is, can a graph's vertices be colored with three colors so that no two vertices of the same color are connected by an edge? Naturally, as the number of edges in a graph increases (keeping the number of vertices fixed), so too does the chance that the answer is no. In addition to discussing the graph-coloring threshold for the number of edges in a graph, Hayes shows how the solvability-unsolvability boundary relates to phase transitions in physics.
--- Mike Breen