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
The EVATAR is a working model of a reproductive system made from a mouse ovary and bits of a human uterus, cervix, vagina, fallopian tubes, and liver. Developed by Northwestern University researcher Teresa Woodruff and her colleagues, the EVATAR is intended to help better test the effects of medicines and toxins on women. And now […]
Texas State University’s Body Farm (AKA Forensic Anthropology Center at Texas State University or FACTS) is a 45-year-old facility where the corpses of medical body donors are left to decompose so that researchers can observe the rate at which human remains are consumed by the elements, scavengers and microbes, allowing them to accurately date the […]
A better understanding how a sperm swims its way toward an egg could help inform new treatments for male infertility. Researchers from the University of York have now come up with a mathematical formula to model how large numbers of moving sperm interact with fluid they’re swimming through. From the University: By analysing the head […]
Thread count isn’t like one of those deceiving metrics like camera megapixels or Facebook friends—more threads are always better if you can afford them. If price was no object, we would all be snoozing soundly bundled up in 1.8 kilo-thread sheets every single night. Guess what? Price doesn’t have to be an object with this […]
Maybe it’s entirely because of podcast ads, but drag-and-drop tools like Squarespace have gotten immensely popular in recent years. While it’s definitely a great tool for any non-coders who want to get a small website up and running quickly, managing content with a primarily visual interface can become a pain once you have more than […]
When you can’t wait for the world’s longest meeting to end, the mindless leg bouncing makes your boredom obvious and just annoys everybody else. Everyone knows the TPS reports need the damn cover sheet, but some sadistic colleague keeps forgetting, probably on purpose just to eat into your lunch hour. Enough is enough!While serving a […]