The 50-year-old Problem That Eludes Theoretical Computer Science

A solution to P vs NP could unlock countless computational problems -- or keep them forever out of reach. MIT Technology Review: On Monday, July 19, 2021, in the middle of another strange pandemic summer, a leading computer scientist in the field of complexity theory tweeted out a public service message about an administrative snafu at a journal. He signed off with a very loaded, 'Happy Monday.' In a parallel universe, it might have been a very happy Monday indeed. A proof had appeared online at the esteemed journal ACM Transactions on Computational Theory, which trades in 'outstanding original research exploring the limits of feasible computation.' The result purported to solve the problem of all problems -- the Holy Grail of theoretical computer science, worth a $1 million prize and fame rivaling Aristotle's forevermore.

This treasured problem -- known as 'P versus NP' -- is considered at once the most important in theoretical computer science and mathematics and completely out of reach. It addresses questions central to the promise, limits, and ambitions of computation, asking:

Why are some problems harder than others?

Which problems can computers realistically solve?

How much time will it take?

And it's a quest with big philosophical and practical payoffs. 'Look, this P versus NP question, what can I say?' Scott Aaronson, a computer scientist at the University of Texas at Austin, wrote in his memoir of ideas, Quantum Computing Since Democritus. 'People like to describe it as 'probably the central unsolved problem of theoretical computer science.' That's a comical understatement. P vs NP is one of the deepest questions that human beings have ever asked.' One way to think of this story's protagonists is as follows: 'P' represents problems that a computer can handily solve. 'NP' represents problems that, once solved, are easy to check -- like jigsaw puzzles, or Sudoku. Many NP problems correspond to some of the most stubborn and urgent problems society faces. The million-dollar question posed by P vs. NP is this: Are these two classes of problems one and the same? Which is to say, could the problems that seem so difficult in fact be solved with an algorithm in a reasonable amount of time, if only the right, devilishly fast algorithm could be found? If so, many hard problems are suddenly solvable. And their algorithmic solutions could bring about societal changes of utopian proportions -- in medicine and engineering and economics, biology and ecology, neuroscience and social science, industry, the arts, even politics and beyond.

Read more of this story at Slashdot.