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
Mathematician Stephen Wolfram and his company do a lot of consulting for Hollywood. But he doesn’t often do it on an urgent basis because a movie is about to shoot and they neglected to “tech the tech.” When I first started looking at the script for [Arrival], I quickly realized that to make coherent suggestions […]
Can you “hear” motion or light flashes? If so, according to new research from City University London, you may be experiencing a not-so-rare form of synaesthesia. Synesthesia is the fascinating neurological phenomenon whereby stimulation of one sense involuntarily triggers another sensory pathway. For example, a synesthete might taste sounds or hear colors. (In this study, […]
Scientists declared the ruby seadragon a new species in 2015, but that was based on dead specimens in a museum. Now though, Scripps Institution of Oceanography biologist Greg Rouse who led the team that originally discovered the species, managed to find two of the wonderful fish swimming around the Recherche Archipelago, off the south coast […]
You know as well as I that writing complex, long-long form text requires significant organization. You’re probably also well aware that Word just isn’t up to the task. That’s why I’m a huge fan of Scrivener, the software suite used by best-selling authors and technical writers alike.Scrivener is much more than another digital typewriter. With a […]
Looking to upgrade your weekend? Here are three randomly awesome products on my mind this week.#3 FRESHeBUDS Pro Magnetic Bluetooth EarbudsAs more and more phones and gadgets switch to Bluetooth-only compatibility, you’ll need to get Bluetooth headphones like the rest of us. I’ve been super impressed with these affordable magnetic headphones. Pull the magnetic earbuds apart to auto-connect […]
Traditional folding wallets are designed for paper bills—but these days, carrying cash is rarely a necessity. More often than not, I don’t carry cash at all. This Bogui Clik Wallet is the best answer I’ve found for avoiding the hassle of those tight-fitting credit card pockets.This attractive, minimalist wallet features a protective lip, so my cards don’t […]