One of the most perplexing but rewarding questions in the field of computer science is a question that is relevant in almost every aspect of life, from code-cracking to quantum mechanics.
The concepts of time, space, and complexity in the world of a computer scientist come together in a single million-dollar problem: what is the relationship between complexity classes P and NP?
The person responsible for this conundrum is Professor Stephen Cook, a prominent figure in the field of computer science since his infamous 1971 paper entitled “The Complexity of Theorem Proving Procedures,” where he had productively articulated the problem, but left it unsolved. His work since then has recently earned him the prestigious John L. Synge Award from the Royal Society of Canada.
But what is this problem? In theoretical computer science, problems need resources in order to be solved, meaning tradeoffs often have to be made. In this case, the two resources are time, or how many steps it takes to solve the problem, and space, or how much memory it takes to solve the problem. The two classes, P and NP, designate all problems that fall under certain parametres of time and space, P for simple problems and NP for complex ones.
Consider a traveling salesman who needs to visit several cities of a given distance in separation, but is only allowed to travel a set total distance. Though it may be possible, finding the answer involves calculating countless permutations. If the number of cities were too high, this task becomes an NP problem, like many other analogous problems in this field, and would be practically unfeasible with the computer technology available today.
The famous ‘traveling salesman problem’ is one of the many examples of an NP problem that could be solved if put into a simpler framework, like the algorithms that solve P problems. If the NP and P classes are in fact the same, then increasingly complex problems can be solved with approaches used on much simpler problems. Similar NP problems in cryptography, biochemistry, and quantum theory will be efficiently solvable, meaning better computer systems like code-cracking software and more accurate biological prediction models.
The importance of this problem has prompted the Clay Mathematics Institute, a private foundation dedicated to the proliferation of mathematical knowledge, to offer a million-dollar prize to anyone who can solve this puzzle.
In search of a proof, Cook’s work has rendered several NP problems solvable through a P problem approach, breakthroughs that have brought mathematicians closer to a general proof that NP and P classes are the same. Because of the insurmountable nature of the problem, attacking the problem from a different angle or attempting a shortcut can lead to a solution, and Cook’s creative approaches have been inspirational to the field.
The applications of Cook’s momentous research have reached the far realms of programming, algebra, and games and puzzles. Its influence continues to spread as the field of mathematics and computer science continues to expand. At the moment, Cook is taking on several endeavors including the P and NP question as well as authoring a book, Foundations of Proof Complexity, with one of his graduate students, Phuong Nguyen.
