Has the Devilish Math Problem "P vs NP" Finally Been Solved?

80beats
By Andrew Moseman
Aug 11, 2010 12:09 AMNov 19, 2019 8:17 PM
Vinay.jpg

Newsletter

Sign up for our email newsletter for the latest science news
 

P is not equal to NP. Seems simple enough. But if it's true, it could be the answer to a problem computer scientists have wrestled for decades. Vinay Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. Mathematicians are reviewing his work now—a task that could go on for a long time. If he's correct, Deolalikar will have figured out one of the Clay Mathematics Institute's seven Millennium Prize Problems, for which they give $1 million prizes. (Grigory Perelman won one of the seven for solving the Poincaré conjecture, but turned down the money last month.) What's all the hubbub? First, an explainer:

The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P. If the answer to a task can be checked quickly then it is in class NP [New Scientist].

That definition is pretty abstract, so here's a more concrete example:

Clay imagines a college housing scenario wherein 400 students have applied for rooms at a college that can only accommodate 100 of them. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together. The total possible number of pairings is ridiculously large -- more than the total number of atoms in the universe -- but the solutions, i.e. the list of pairings finally provided to the dean, is easy to check for errors: If one of the dean's prohibited pairs is on the list, that's an error [AOL News].

Thus, if P were equal to NP, it would mean that problems that are easy to check—like this roommate match-up—must also be easy to solve. But if Deolalikar is correct and in fact P is not equal to NP, as many mathematicians already believed

, then that ain't necessarily so. And that would have practical meaning, according to Michael Sipser of MIT.

Sipser ... says that the P-versus-NP problem is important for deepening our understanding of computational complexity. “A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says [MIT News].

Deolalikar's proof is now available to read online

. New Scientist

and Network World

report that he pulled together tactics from different disciplines to show that an NP problem—whether a list of statements can be simultaneously correct or contradict one another—is not a P problem, because it can be easily checked but no computer can figure it out quickly from scratch. In the days since the proof began to spread across the Internet, however, some math bloggers like Scott Aaronson

have responded to the proof by saying yes, it's lovely, but no, it probably isn't going to stand. Related Content: 80beats: Brilliant & Reclusive Russian Mathematician Doesn't Need Your Prize Money

80beats: Can a Google Algorithm Predict Nobel Prize Winners?

DISCOVER Interview: The Math Behind the Physics Behind the Universe

DISCOVER: Top Math Stories of 2006

, featuring Perelman’s achievement Image: HP Labs

1 free article left
Want More? Get unlimited access for as low as $1.99/month

Already a subscriber?

Register or Log In

1 free articleSubscribe
Discover Magazine Logo
Want more?

Keep reading for as low as $1.99!

Subscribe

Already a subscriber?

Register or Log In

More From Discover
Recommendations From Our Store
Stay Curious
Join
Our List

Sign up for our weekly science updates.

 
Subscribe
To The Magazine

Save up to 40% off the cover price when you subscribe to Discover magazine.

Copyright © 2024 Kalmbach Media Co.