1. On Monday, July 19, 2021, in the middle of another strange pandemic summer, a leading computer scientist in the field of complexity theory tweeted

The 50-year-old problem that eludes theoretical computer science

submited by
Style Pass
2021-10-28 03:00:09

1. 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 

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: 

“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.” 

Leave a Comment