The Most Important Open Problem .

I often get asked which open problem in science I think is the most important.¹ I always respond, “does P = NP?”²

A mathematically-inclined (and perhaps jocular) reader at this point will think “yes, when N=1." A reader with a background in computer science (but is not, say, a theoretical computer science professor) will gaze in the foreground, trying to remember the contours of this problem from their algorithms class. A reader who is struggling to understand the footnotes will also probably not understand how the prose got to this point, along with the reader who was skimming these words (and is daydreaming by now).³ The rest will hope that I elaborate on what “P = NP” is very soon. Well, here it is reader:

The P vs NP problem is the most famous open question in computer science.⁴ In a few words, the problem is: “if we can check a solution quickly, does that mean we can could have found that solution quickly?”⁵ Here, P refers to the problems that can be solved quickly, and NP refers to the problems that can be verified quickly.⁶ Thus, “P = NP” means that if a solution to a problem can be verified quickly, then the solution itself can be found quickly.

The canonical example of this is Sudoku. For this game, we can write a program to check whether or not a solution is valid quickly; however, as Sudoku grids grow larger, the time to solve it grows exponentially; thus, there is no known program which can start with a blank grid and fill in all the squares quickly. Computer scientists (and Sudoku lovers) are asking: “will we ever find a better program?”⁷ In many cases, a problem seemed slow until someone found a quick program for it, but others, like Sudoku and and the Traveling Salesman problem, remain “slow.”

Most computer scientists believe that P != NP, but no one has found a proof yet.⁸ I personally hope that P = NP because this is the chaotic evil scenario, as this would break our existing cryptography systems and probably everything else we hold near and dear. (In the words of one computer scientist: “If P = NP then public-key cryptography is impossible”).⁹

Solving this problem either way would have massive implications for the world. The P vs NP problem is one of the Clay Institute Millennium Problems, a “Most Wanted” list of open problems in math and physics where a solution holds a 1 million dollar bounty. I think P vs NP is the most important problem because it is like a key to unlocking the rest of the universe’s mysteries.