P â‰ NP: To begin with. There is (almost) no doubt whatever about that.
Why? To quote Scott Aaronson—an MIT complexity researcher interviewed in an excellent article on Technology Review about the background of the "P vs. NP" problem—if P = NP then, "we'd be living in a fundamentally different universe, and we'd probably have noticed by now."
Naturally, that leads to another, "Why?", which author John Pavlus answers cleanly and clearly:
"P versus NP" is more than just an abstract mathematical puzzle. It seeks to determine--once and for all--which kinds of problems can be solved by computers, and which kinds cannot. "P"-class problems are "easy" for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for "NP" problems, a solution might be very hard to find--perhaps requiring billions of years' worth of computation--but once found, it is easily checked.
The "P versus NP problem" asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem. If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers' problem-solving powers will remain fundamentally and permanently limited. Practical experience overwhelmingly suggests that P does not equal NP. But until someone provides a sound mathematical proof, the validity of the assumption remains open to question.
That's why P vs. NP matters. And it's why P probably â‰ NP. "But wait," you ask, "Wasn't this solved, like, a couple weeks ago."
Sadly, no. The proof offered by HP labs researcher Vinay Deolalikar isn't standing up very well against scrutiny and is not likely, at this point, to earn him the $1 million prize still up for grabs.
Technology Review: What does "P vs. NP" mean for the rest of us?
Some rights reserved by stuartpilbrow
University of Zurich researchers used transcranial magnetic stimulation, a noninvasive method of inhibiting activity in parts of the brain, to “turn off” people’s ability to control their impulses. They focused on the temporoparietal junction, an area of the brain thought to play an important role in moral decisions, empathy, and other social interactions. They hope […]
Are you jonesing for a dose of optimism and possibility? In the mood to contemplate the cosmos? Want to experience a musical message for extraterrestrials the way it was meant to be played? The Voyager Golden Record: 40th Anniversary Edition, a project I launched with Timothy Daly and Lawrence Azerrad, is a lavish vinyl box […]
In Rich do not rise early: spatio-temporal patterns in the mobility networks of different socio-economic classes, a group of transportation engineers analyze an open data-set about the commutes of people in the Colombian cities of Medellín and Manizales, concluding that the rich and the poor commute the furthest distances, but that the rich have much […]
Nothing is more frustrating than needing to edit or sign a PDF and not having access to the original document. That’s why PDFpenPRO is a must-have app in our books.With this extremely useful app, you can merge, markup, and create PDF documents without ever having to convert your PDFs into word processor file formats. Type directly onto […]
From self-driving cars to stock market predicting software to the recommendations you get on Amazon and Netflix, machine learning is at the core of modern technology. You could find yourself building technology that is literally changing the world with the skills you’ll learn in The Complete Machine Learning Bundle. This bundle of 10 courses includes 406 lessons that will teach […]
This Python Mega Course will help you learn to code by teaching you to build 10 real-world apps that each highlight a unique use of Python.Job prospects for coders are still growing steadily—and with Python being one of the most popular coding languages out there today, it’s important for job seekers to demonstrate a widespread understanding of the […]