Communications of the ACM
The Bbva Foundation Frontiers of Knowledge Award Goes to Stephen Cook
1982 ACM A.M. Turing Award winner Stephen Cook has won the BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category for his pioneering and influential work on computational complexity.
Credit: Natural Sciences and Engineering Research Council of Canada
Computer scientist Stephen Arthur Cook has been granted the BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category "for his important role in identifying what computers can and cannot solve efficiently," in the words of the jury's citation. His work, it continues, "has had a dramatic impact in all fields where complex computations are crucial."
Before deciding how to tackle a problem, we must first know whether it is solvable within a reasonable length of time. Cook identified a specific class of problem, termed NP-complete, whose defining trait, as he explained yesterday after being told of the award, is that "if you can show that a problem is NP-complete, then very likely you should give up trying to solve it."
This wisdom to know when there is no point trying may smack of defeatism, but from a practical standpoint the opposite is true. For, as he says, rather than waste time attempting the impossible, programmers can concentrate on "far more useful strategies, such as seeking out approximate solutions."
Cook is professor of computer science at the University of Toronto; he was the recipient, in 1982, of the ACM A.M. Turing Award. His nominators describe his contribution as standing alongside Turing's concept of "computability" as a cornerstone of the mathematical foundations of computing. While Turing defined what computers can and cannot solve, Cook added to the mix the principle of efficiency, so the question became what is or is not efficiently computable.
"There are problems that a computer could feasibly solve, except that it would take until the sun burns out," Cook points out. "These are problems of the class we call NP. And then we have the class that we call P, which can be solved within an acceptable time frame. The trick is to decide which problems are NP [not efficiently solvable], and which are P [easily solvable].
From Virtual-Strategy Magazine
View Full Article
No entries found