Sign In

Communications of the ACM

ACM News

The 50-Year-Old Problem That Eludes Theoretical Computer Science

View as: Print Mobile App Share:
The Steiner tree problem: Connect a set of points with line segments of minimum total length.

This treasured problemknown as P versus NPis considered at once the most important in theoretical computer science and mathematics and completely out of reach.

Credit: Derek Brahney

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.

From MIT Technology Review
View Full Article



Adam Kutell

This is the worst article I've ever seen. It has zero content in it whatsoever, except for a link to the "full article" that hits a paywall for any reader who is not an MIT alum. Get your act together, ACM.

CACM Administrator

Dear Adam Kutell,
The CACM website publishes aggregated content with links to original, full content, some of which requires a subscription.

Displaying all 2 comments