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
Scientists discovered this new species of “glass frog” in Ecuador’s Amazon lowlands. Hyalinobatrachium yaku’s belly is so transparent that you can clearly see its kidneys, bladder, and beating heart. From Science News: Yaku means “water” in Kichwa, a language spoken in Ecuador and parts of Peru where H. yaku may also live. Glass frogs, like […]
Jennifer Raff — a bioanthropologist and geneticist who researches and teaches at U Kansas and U Texas — provides some excellent advice and context on how to read a scientific paper, from figuring out which papers and journals are worthy of your attention to understanding the paper in its wider context in the relevant field.
Apple released this lovely new commercial featuring Carl Sagan reading from his magnificent 1994 book Pale Blue Dot: A Vision of the Human Future in Space, now available as an audiobook. This surprising partnership spurred Adweek to interview my friend Ann Druyan, Sagan’s wife, collaborator, and creative director of the Voyager Golden Record, about being […]
Learning a new language will give your resume an upgrade, sure, but it will also provide a huge cognitive boost for mental tasks outside of translation and conversation. Bilingual brains have been shown to be better at handling multiple concurrent tasks, and gaining fluency in a new tongue is an amazing way to improve memory, […]
If you struggle to get a good night’s rest, consider replacing your pillows before dropping hundreds on a new mattress. You can give your tired neck a break with a 2-pack of memory foam pillows, available now in the Boing Boing Store.Each of these pillows is stuffed with cooling polyurethane foam that molds to your […]
Although flagship smartphones are unlikely to adopt heavy-duty outer casing anytime soon, you can always prepare your device for the outdoors with a beefy case and and an external battery like this Nomad Tile Trackable PowerPack, available in the Boing Boing Store for $119.95.The Nomad Tile can fully recharge an iPhone 7 over three times […]