Stephen Cook, Frontiers of Knowledge Award in Information and Communications Technologies
U.S. mathematician 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. His work has had a dramatic impact on all fields where complex computations are crucial.
Stephen 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. 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].”
In this video you can see the first interview with Stephen Cook after being notified of the awarding of the prize.
A Millennium Problem
Cook’s studies gave rise to what is now considered one of the great open questions in mathematics: “P vs. NP", included on the seven-strong list of “Millennium Problems” of the Clay Mathematics Institute (United States), each one worth a one-million-dollar prize.
In non-technical terms, “P vs. NP” conjectures whether there may not exist some faster way, some brilliant shortcut, that allows NP problems to be solved.
Cook’s central achievement was to identify a sub-class of NP problems which he termed NP-complete, whose distinguishing features are, firstly, that they are the hardest and, secondly, that they are computationally equivalent; i.e., finding an efficient algorithm for one would yield algorithms for all the rest, and not just for the sub-set of NP-complete problems, but for NP problems as a whole.
The NP-complete class of problems that he described are “key” in a very real sense, because in the event that they yielded to algorithmic solution, “then all problems in NP could be easily solved,” explains Cook.
If such an algorithm should appear, the implications are enormous, because Internet security systems, and therefore the whole digital economy, rests on the assumption no one can efficiently break encrypted code in a reasonable amount of time.
Today, the vast majority of mathematicians believe no such algorithm exists, meaning problems in NP are genuinely unsolvable. But no one has proved this.