Over the course of 50 years he published numerous papers regarding computational complexity. Most notably, "The Complexity of Theorem Proving Procedures" in 1971 proving the existence of the NP-Complete class and coming up with the method of Polynomial-time reduction. Cook proved the existence of NP-Completeness by showing the Boolean satisfiability problem is NP-Complete. The work he has done on Polynomial-time reduction is also notable. Polynomial-time reduction method compares two similar problems, if a polynomial solution can be found from one of them; a solution exists for the other. Other work he has done include contributions to programming languages and logic, parallel computation, and artificial intelligence.
In 1982, Cook was awarded the ACM Turing Award for his contributions to the computational community. The Turing Award is the most prestigious award given to recognize the highest contributions in the field of computer science. By laying the foundations of NP-Complete, Cook had opened the gates to the most actively researched computer science topic to date, the P vs NP problem. The question whether or not P = NP still remains unsolved and the Clay Mathematics Institute (CMI) has offered up to $1 million for anyone who can come up with a solution. More information is available on P vs NP in my first blog.
References
Cook, S. (n.d.). Stephen A. Cook. Retrieved May 10, 2015, from http://www.cs.toronto.edu/~sacook/
Cook, S. (1983). An overview of computational complexity. Communications of the ACM, 400-408.
Dblp: Computer science bibliography. (n.d.). Retrieved May
10, 2015, from http://dblp.uni-trier.de/pers/hd/c/Cook:Stephen_A=.html
P vs NP Problem. (n.d.). Retrieved May 10, 2015, from
http://www.claymath.org/millenium-problems/p-vs-np-problem
No comments:
Post a Comment