Stephen Cook & Leonoid Levin

Cook formalized the notions of polynomial-time reduction and and NP-completeness. This theorem was proven independently by Leonid Levin in the Soviet Union, and has thus been given the name the Cook-Levin theorem.

NP-completeness provides a way to characterize the difficulty of computational problems with respect to the time, that is, the maximum number of computational steps required to solve a problem, as a function of input size. (travelling salesman problem)

P vs. NP has enormous practical implications. When a consumer buys a product over the Internet using a credit card, that transaction is secured with a seemingly unbreakable mass of coding. “The security assumption is based on an unproven fact that no computer can do it,” Dr. Cook explains. Modern-day cryptography rests on the same assumption. Anyone who proves that P does equal NP would undermine the foundations of code-breaking, e-commerce and digital privacy.

Cook showed that certain problems in NP, now known as NP-complete problems, are as hard to solve as any others in NP, in the sense that if any one of these problems is easy to solve, then all problems in NP are easy to solve. Cook’s paper also was the source of the celebrated and still unsolved P versus NP question, which asks whether there are indeed problems in NP which are not in P, that is, problems whose solutions are easily verified but are not easily solved.

Leave a Reply

Your email address will not be published. Required fields are marked *