A Life Dedicated to Four Symbols
Professor Michael Sipser has devoted nearly five decades to exploring a key question about the limits of computation.
Michael Sipser, Professor of Mathematics and former Dean of Science, first heard about the problem of P vs. NP in 1974. Half a century later, he still has his mind on it.
The question of P vs. NP has informally been around since the 1950s and was formalized in the early 1970s. It asks about the equality of two classes of problems: one with solutions that are easy to find and one with solutions that are easy to check.
After naming the P vs. NP problem one of the hardest unsolved math problems of the second millennium, the Clay Mathematics Institute prepared a reward of a million dollars for the mathematician who proves the correct answer. But for Sipser, the monetary reward does not even begin to encapsulate his excitement: finding the coveted solution would be a defining personal victory, one which he has been striving toward for nearly his entire career.
When Sipser entered graduate school in 1974 at the University of California at Berkeley, he started to think about potential approaches to P vs. NP. P represents the class of problems that can be solved in polynomial time; NP is the class containing problems that can be solved in nondeterministic polynomial time, which means these problems can also be verified for correctness in polynomial time.
At that time, the problem was rather new and unexplored, so it didn’t seem very hard to solve it. Sipser felt that someone would find an answer and a proof within a decade or two. He was so convinced that he made a bet with a fellow graduate student: if, by the end of the 20th century, there was no well-accepted proof that P ≠ NP, Sipser would give his classmate an ounce of gold.
In 2000, Sipser paid up with an American Gold Eagle coin.That coin barely scratches the surface of how much thought Sipser has dedicated to this one problem. He always believed that P and NP are different, but finding the underlying reason has been a challenge that has captivated his attention for decades, becoming the cornerstone of his academic life.
Complexity theory, home to the P vs. NP problem, is the branch of computer science that studies how many resources, such as time or space, on a computer are required to solve a given problem. While complexity theory may seem abstract, the question of P vs. NP arises in everyday life. For example, checking that a friend completed a Sudoku puzzle correctly is simple: just make sure that all digits appear in the rows, columns, and squares, and confirm that there are no duplicates. On the other hand, given a blank Sudoku board, it is much harder to start from scratch and place the numbers correctly. Correct completion of a Sudoku board is considered to be a problem in NP; problems in this class can be quickly checked given a solution (in this case, the placements of the numbers). If there is a quick procedure to find the correct placements of the numbers, then this problem would also be in P, the class of problems that can be solved quickly. It is known that all problems in P lie in NP; the mystery is whether all problems in NP are also in P. Currently, the general consensus is that some problems in NP are not in P, implying that the classes are different. A proof of the equality of the two classes would imply a method of solving generalized Sudoku (on any size of square board) that is enormously faster than exhausting all the possible ways of filling the board.
A proof answering P vs. NP will leave a mark on computing. If it is proven that P and NP are equal, the result could facilitate the development of new algorithms and procedures for solving problems, according to Sipser. This implies a quick process for detecting the existence of a clique in a graph or finding the shortest path around the United States that visits all the most populated cities. If a proof for P ≠ NP is developed (which Sipser hopes will happen in his lifetime), then many computational problems will be accepted as not easily solvable, even amidst the technological advancements coming to fruition.
Despite the real-world benefits of a proof of P vs. NP, Sipser is motivated by the basic and beautiful nature of the problem. He states that without knowing whether P and NP are equal, we do not “really understand computation.”
To gain this important understanding, Sipser has become obsessed with what seems like a simple equality or inequality; it is the “only math problem” he has thought about “for a very long time.” Exploring this question of P vs. NP, Sipser said, “is like going out into the jungle and [getting] lost, with no guide posts, no compass, and no sense of direction.” Many math problems have related theories and examples that serve as a guide for solving them, but for P vs. NP, all the apparent approaches have failed — a good launchpad is missing.
The lack of a convincing starting point has not deterred Sipser. He has constantly been on the hunt for a place to begin. In graduate school, he thought about simpler cases of the problem and proved that machines that can try several solutions at once while solving a problem will use less memory than machines that follow a strict set of rules. This became his PhD thesis. Since then, he has attacked the question from countless angles. The experience has held many highs and lows — the excitement of a new idea as well as the disappointment when it comes to a dead end.
Currently, Sipser is focusing on a version of P vs. NP in a world where computers have infinite computing power, with access to unbounded space and the ability to compute anything instantaneously. The standard version of the problem concerns Turing machines, a model of computation with finite computing power. Sipser believes that the analogy of the infinite model could serve as a guide to a proof for Turing machines. But for now, this idea is simply “the essence of a suggestion of an approach.”
Throughout his seemingly infinite attempts, Sipser has not been able to pinpoint a single line of attack as “the one,” and he noted that a wide variety of approaches have already been taken. For example, Ketan Mulmuley from the University of Chicago employs methods in algebraic geometry, which are very different from Sipser’s ideas in computer science. Throughout his experiences with different ideas, Sipser has often found himself working alone. He believes that many mathematicians avoid this problem because of its difficulty. Nearly everyone has given up.
For some, the truth is that there is no answer. One of Sipser’s students, Zhening Li, stated that some mathematicians believe that the problem is independent of the accepted axioms, or ground rules, in math. As a result, these mathematicians conclude that proving the equality or inequality of the two classes is likely impossible.
Despite the appearance of a lack of results over the past few decades, or even the possible nonexistence of an answer, Sipser remains hopeful. He finds himself coming up with new ideas for proving the inequality of the two classes, and this potential keeps him going. His decades of interaction with the problem have allowed him to gain much insight, and Sipser now sees why some of his old approaches “were just doomed.”
For now, as long as there is no answer to P vs. NP, the true future of computation cannot be foretold; Li bets that the problem will remain unsolved in 2100. Regardless of mathematicians’ attitude toward the problem, Sipser remains firm in his conviction. “This is a fundamental problem,” he stated, “and [mathematicians] should try to solve it.”