The American mathematician Stephen Arthur Cook was awarded the Frontiers of Knowledge Award of the BBVA Foundation in the category of Information Technology and Communications for helping to define what can not solve problems efficiently computers and what yes.
This research has had “a decisive impact on those areas where complex calculations are of vital importance,” according to the ruling issued today a prize of 400,000 euros ($ 436,000).
The work of Cook, 76 and Professor of Computer Science at the University of Toronto, has been appointed, by the concept of computability Alan Turing, one of the milestones in the mathematical foundation computer.
“The theory of Turing defined the complexity, my contribution was the introduction of the NP-Complete class. I just try to prove that there are problems that a computer will not solve effectively, so do not waste your time trying to work something unsolvable, find approximate solutions, “said the mathematician in a telephone set during the press conference to announce the winner.
According to Cook, there are problems that can be solved in principle by a computer, but the machine it takes so long that the sun would die before. Those are the problems called NP. And there are the so-called P, which itself can be solved in a reasonable time. “The question is to decide which problems are NP (not soluble efficiently), and which are P (readily soluble),” said
.
The main contribution of Cook was determined that within the NP class is a subclass -NP completely, and whose distinctive features are that, besides being the most difficult, is computationally equivalent; that is, if an efficient one algorithm be found, mean that there is an algorithm for the rest and not just the complete NP, but to the set of NP.
Cook insisted there NP complete problems-not soluble eficientemente- that “could take thousands of years to resolve,” which stands as the jury had not been able to prove.
The president of the jury, Georg Gottlob is is “a decisive contribution” and “an important contribution in daily life”, and that “everywhere there to solve NP-complete problems.”
Cook’s work, published in 1971, shortly after doctorarse- led to what is now considered one of the major unsolved problems of mathematics, considered one of the seven “Millennium Problems” the Clay Mathematics Institute, Gottlob said.
Forty-five years of effort have failed to find an efficient algorithm for NP complete problems and meet, the encryption system and the security of digitally-bases economy would be compromised, experts warn.
Currently thousands of NP complete problems in many different areas literally know. biology, physics, economics, number theory, logic or optimization
An example is the way in which proteins acquire their structure D, a major problem in biology; another is the famous traveling salesman problem: find the most efficient route to be followed by a delivery to reach many recipients
Just one year after the publication of the work of Cook, another mathematician published a list of a few. NP complete three hundred problems.
The Frontiers of Knowledge Awards were created in 2008 and are awarded in eight categories such as Climate Change, Biomedicine or Financial Economics, among others.
It is anticipated that the awards are delivered next June in Madrid. See Also “Black holes, so strange mathematical solutions that capture our attention” Shahen Hacyan
See Also Mayans Mathematics, more effective method for primary school children See Also Mexico obtained six medals in International Mathematical Olympiad
No comments:
Post a Comment