A strange new family of algorithms probes the boundary between
easy and hard problems Why are some computational problems so
hard and others easy? This may sound like a childish, whining
question, to be dismissed with a shrug or a wisecrack, but if
you dress it up in the fancy jargon of computational complexity
theory, it becomes quite a serious and grownup question: Is P
equal to NP? An answer—accompanied by a proof—will get you a
million bucks from the Clay Mathematics Institute. I'll return
in a moment to P and NP, but first an example, which offers a
glimpse of the mystery lurking beneath the surface of hard and
easy problems. Consider a mathematical graph, a collection of
vertices (represented by dots) and edges (lines that connect the
dots). Here's a nicely symmetrical example: Is it possible to
construct a path that traverses each edge exactly once and
returns to the starting point? For any graph with a finite
number of edges, we could answer such a question by brute force:
Simply list all possible pat