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

Log in to view the full text

Log in through your institution

Log in through your institution


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.