Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo


Unsupported browser: Your browser does not meet modern web standards. See how it scores »

{ action.text }

For example, our inability to efficiently factor huge composite numbers (a classic NP problem) forms the basis of modern cryptography–which undergirds everything from national security to purchases. “We don’t need a formal proof that P is not equal to NP in order to rely on the conjecture,” Aaronson says. “Programmers know about the problem and would be excited to see P does not equal NP proved, but on a day-to-day level, they know that reformulating [an NP problem] into something easier makes much more sense than trying to solve the mathematical problem of the century.”

Because NP-class problems are so pervasive (even sudoku puzzles and airline-schedule searches on are computationally “hard”), innovative workarounds are constantly being discovered. Stochastic optimization, for example, mimics the randomness found in physical systems (such as cooling metals or mutating DNA) in order to produce “good enough” solutions instead of computationally hard ones.

Attempts to “cope with” the assumption that P does not equal NP “help us develop new mental technologies,” says Richard Lipton, a computer scientist at Georgia Tech who studies the P versus NP problem. “Even though we’ve been writing algorithms for decades, we don’t fully understand what they’re capable of,” he continues. “So even if you proved that P does not equal NP–something that everyone already believes–it would have to radically expand our understanding of those capabilities, and make many new things possible with computers, in addition to all the clever workarounds we’ve already found.”

So if incremental progress can still generate useful innovation, why aren’t titans of industrial research like Google, Microsoft, and HP (all of whom declined to comment for this article) devoting huge teams of researchers to the P does not equal NP puzzle? “Proving a negative is just incredibly hard, and from [a large company’s] point of view, it probably doesn’t have much impact on the next financial quarter or even the next few years of their business,” says Lipton. “It’s more of a long-term issue.”

Of course, there’s always the alternative: proving that P does in fact equal NP. But don’t hold your breath, says Aaronson. “There are good reasons why very few people believe that P equals NP,” he says. “If it did, we’d be living in a fundamentally different universe, and we’d probably have noticed by now.”

18 comments. Share your thoughts »

Credit: Technology Review

Tagged: Computing, computing, cryptography, HP, encryption, computer science, math, mathematics

Reprints and Permissions | Send feedback to the editor

From the Archives


Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me