Research NewsMathematics

Taking ‘Hard’ Problems to the Limit

See allHide authors and affiliations

Science  14 Mar 1997:
Vol. 275, Issue 5306, pp. 1570
DOI: 10.1126/science.275.5306.1570a

You are currently viewing the summary.

View Full Text

Summary

SAN DIEGO—Limits—a term often bandied in calculus class—are the “endpoints” of infinite processes. The concept hasn't played much of a role in theories of purely finite processes such as computing, which takes place in finite-sized machines. But a new proposal suggests that limits could be key to solving a famous question in computer science: whether certain problems, such as the Traveling Salesman Problem, are “hard,” meaning they cannot be solved efficiently by any computer algorithm.