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
James Delingpole is an invective-hurling anti-climate science columnist who has candidly admitted that he doesn’t bother to read scientific papers, calling himself a “an interpreter of interpretations.”
Kratom (previously) is a widely used herb that has been very effective in treating opioid withdrawal and other chronic, hard-to-treat conditions — it also became very controversial this year because the DEA decided, without evidence, to class it as a dangerous drug, and then changed its mind (unprecedented!) after a mass-scale petition that included interventions […]
In a curious study, researchers at the University of California, Los Angeles showed that transcranial magnetic stimulation (TMS) — altering brain activity by zapping specific regions with magnetic pulses — can apparently increase people’s libido, at least briefly. Neuroscientist Nicole Prause and her colleagues targeted the left dorsolateral prefrontal cortex (at the left temple), a […]
Loot Crate is a totally different kind of subscription service that mails subscribers monthly boxes filled with curated geek, pop culture, and gamer paraphernalia. Its cult following awaits a box every month filled with everything from bobble heads to T-shirts to special edition collectibles. But nothing gets Loot Crate fans as excited as the limited […]
The ARMOR-X Mini Flexible Phone Tripod is a smartphone tripod that is designed with flexible legs to rest on virtually any type of surface. Other tripods have proved useless unless I conveniently have a flat surface in front of me, which is why this particular tripod was appealing enough to try out. The ARMOR-X is compact and easy […]
You don’t need to get an advanced degree and take out massive loans to become a coder. This bundle of 10 courses was designed to teach anyone to code at home for less than it costs to go out for dinner. I was particularly impressed with this new 2017 bundle because it includes courses on […]