Logo IMG


On the Threshold

Brian Hayes

Last night I called technical support for the universe to report a bug. They kept me on hold for eternity, but finally I lodged my complaint: Some things in this world take entirely too long to compute—exponentially so, in the worst cases. "That's not a bug, that's a feature," was the inevitable reply. "It keeps the universe from running down too fast. Besides, NP-complete calculations are an unsupported option, which void your warranty. And where is it written that anything at all is guaranteed to be efficiently computable? Count yourself lucky that 1+1 is a polynomial-time calculation."

Perhaps cosmic tech support is right: Quick and easy answers to computational questions are not something we are entitled to expect in this world. Still, it's puzzling that some calculations are so much harder than others. The classic example is multiplication versus factoring. If you are given two prime numbers, it's easy to multiply them, yielding a bigger number as the product. But trying to undo this process—to take the product and recover the two unknown factors—seems to be much more difficult. We have fast algorithms for multiplying but not for factoring. Why is that?

Although such questions stump the help desk, there has been some progress lately in understanding the sources of difficulty in at least one family of computational tasks, those known as constraint-satisfaction problems. The new line of inquiry doesn't quite explain why some of these problems are hard and others are easy, but it traces the boundary between the two classes in considerable detail. Furthermore, a better map of the problem-solving landscape has led to a novel algorithm that pushes back a little further the frontier of intractability. The algorithm, called survey propagation, could well have important practical applications.

comments powered by Disqus


Of Possible Interest

Feature Article: The Statistical Crisis in Science

Computing Science: Clarity in Climate Modeling

Engineering: Anonymous Design


Foreign-Language PDFs


Subscribe to American Scientist