Once a week.
Subscribe to our weekly newsletter.
The math problem that could change the world: Does P = NP?
Depending on the answer, one of the famous unsolved Millennium problems could have major implications in our lives.
- The Millennium Prize Problems are a set of seven unsolved mathematical problems laid out by the Clay Mathematical Institute, each with a $1 million prize for those who solve them.
- One of these problems asks whether P = NP. Put simply, this asks whether computationally hard problems actually contain hidden, computationally easy solutions. This, however, is a major simplification.
- Proving that P does not equal NP would be a major milestone, and it's the result that most computer scientists expect. However, if the opposite is true, then our world would become drastically different than it is now.
In 2000, the Clay Mathematics Institute laid out seven unsolved mathematical problems and offered $1 million to anyone who could resolve them. So far, only one of the seven so-called millennium problems have been solved: the Poincaré Conjecture, which has to do with how to define spheres in different spatial dimensions.
For non-mathematicians, both the nature of this problem and why it would be worth $1 million is a little hard to wrap one's head around. However, another millennium problem is a little easier to understand, and solving it would have drastic consequences for how our world functions. Although seemingly more straightforward, definitively proving this problem one way or another has eluded researchers for decades. The question is whether or not P = NP.
What are P and NP problems?
Put simply, the P versus NP question asks whether the set of problems that can be easily solved are also in the set of problems that can be easily checked. Imagine you're tasked with gluing a shattered teacup back together. It's easy to see if you've succeeded—you'll have a complete teacup in front of you. But it's very hard to take all the disparate pieces and fit them back together. This is an example of an NP problem; hard to solve, easy to check.
Now imagine instead you were tasked with counting how many pieces the teacup had broken into rather than having to reassemble it. This would be a P problem. It's comparatively easier to count the broken pieces than it is to figure how they connect to each other.
Why are these two problem sets called P and NP?
Computer algorithms take a certain amount of time to solve the problem they are tasked with. Generally, you can roughly estimate how much time an algorithm will take using the number of elements they need to handle. Computer scientists call the number of elements N.
Because some algorithms are more or less efficient than others, the time they take to complete could be related to N, N2, N3, and so on. The important thing, though, is that the exponent is a constant—it's 1, or 2, etc. When this is the case, an algorithm is said to complete in polynomial time, or P.
Unfortunately, not all problems work this way. Solving some problems can take an algorithm an amount of time proportional to 2N, 3N, and so on. In this case, N is the exponent, meaning that every element the algorithm has to deal with increases its complexity exponentially. In this case, the algorithm can be completed in exponential time, or NP (which really stands for nondeterministic polynomial time).
The difference between these two can be huge. If a P algorithm has 100 elements, and its time to complete working is proportional to N3, then it will solve its problem in about 3 hours. If it's an NP algorithm, however, and its completion time is proportional to 2N, then it will take roughly 300 quintillion years.
Why does this matter?
Flickr user Jan Kaláb
Another way to ask whether P = NP is to ask whether every hard problem actually contains an easy, but hidden, solution. Are these two flavor of problems irrevocably separate from one another? Are some problems simply complex by their fundamental nature?
If P does equal NP, then it would have some major implications for our way of life. One major benefit is that many NP problems are referred to as being NP-complete, which means that their solutions can be quickly adapted to any other NP-complete problem. So, developing a way to quickly solve one NP-complete problem would make significant strides towards completing all other NP-complete problems.
What are some examples of NP problems? Many researchers focus on one major concern. The majority of modern cryptography relies on codes that are hard to crack but easy to check. As an example, consider the passwords or PINs to your various accounts. Checking that they are correct is straightforward, but brute-force guessing every permutation of letters and numbers would take forever. The encryption behind securing your credit card number when ordering something on Amazon, too, is an example of NP cryptography. If P = NP, then cracking nearly every kind of encryption would suddenly become much, much easier.
While losing any semblance of internet security would be disastrous, there would be many beneficial consequences if P = NP. Lance Fortnow, a computer scientist and author of The Golden Ticket: P, NP and the Search for the Impossible, summed up some of the major consequences in an article for Communications of the ACM:
Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface. Learning becomes easy by using the principle of Occam's razor—we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.
This issue of whether P = NP is so fundamental that it's difficult to select only a handful of representative tasks that could be improved by light years. It would become comparatively easy, for example, to predict protein structures from their amino acid sequences, an important milestone for designing drugs and biotechnology. Another commonly cited NP problem is how to determine the most efficient layout of transistors on a computer chip, significantly boosting computing power.
In fact, proving P = NP would make it much, much easier to solve nearly all other mathematical problems. Fortnow also wrote that "A person who proves P = NP would walk home from the Clay Institute not with $1 million check but with seven (actually six since the Poincaré Conjecture appears solved)."
Ultimately the consequences of proving that P = NP would be the total upending of the current technological and economical underpinnings of society. In all likelihood, solving this problem would be an innovative boost on par, if not greater than, the invention of the internet.
The scientific consensus
Unfortunately, most computer scientists do not believe that P = NP—as of 2012, 83% of computer scientists did not believe this proposition to be true. It's very difficult to prove a negative, but all the failed attempts to prove that P = NP lend credence to the idea that the two types of problems are ultimately irreconcilable. MIT scientist Scott Aronson wrote a blog post listing ten reasons why P most likely does not equal NP, and number nine lays out an argument that both significantly dispels the idea that P = NP and succinctly describes the consequences were it true:
If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps,' no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.
Anyone can be a math person – once they understand this.
- 'Magic square' math puzzle has gone unsolved since 1996 - Big Think ›
- ‘Migration map’ of elite mathematicians reveals identity-based disparities - Big Think ›
Evolution doesn't clean up after itself very well.
- An evolutionary biologist got people swapping ideas about our lingering vestigia.
- Basically, this is the stuff that served some evolutionary purpose at some point, but now is kind of, well, extra.
- Here are the six traits that inaugurated the fun.
The plica semilunaris<img class="rm-lazyloadable-image rm-shortcode" type="lazy-image" data-runner-src="https://assets.rebelmouse.io/eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpbWFnZSI6Imh0dHBzOi8vYXNzZXRzLnJibC5tcy8xOTA5NjgwMS9vcmlnaW4ucG5nIiwiZXhwaXJlc19hdCI6MTY3NDg5NTg1NX0.kdBYMvaEzvCiJjcLEPgnjII_KVtT9RMEwJFuXB68D8Q/img.png?width=980" id="59914" width="429" height="350" data-rm-shortcode-id="b11e4be64c5e1f58bf4417d8548bedc7" data-rm-shortcode-name="rebelmouse-image" />
The human eye in alarming detail. Image source: Henry Gray / Wikimedia commons<p>At the inner corner of our eyes, closest to the nasal ridge, is that little pink thing, which is probably what most of us call it, called the caruncula. Next to it is the plica semilunairs, and it's what's left of a third eyelid that used to — ready for this? — blink horizontally. It's supposed to have offered protection for our eyes, and some birds, reptiles, and fish have such a thing.</p>
Palmaris longus<img class="rm-lazyloadable-image rm-shortcode" type="lazy-image" data-runner-src="https://assets.rebelmouse.io/eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpbWFnZSI6Imh0dHBzOi8vYXNzZXRzLnJibC5tcy8xOTA5NjgwNy9vcmlnaW4uanBnIiwiZXhwaXJlc19hdCI6MTYzMzQ1NjUwMn0.dVor41tO_NeLkGY9Tx46SwqhSVaA8HZQmQAp532xLxA/img.jpg?width=980" id="879be" width="1920" height="2560" data-rm-shortcode-id="4089a32ea9fbb1a0281db14332583ccd" data-rm-shortcode-name="rebelmouse-image" />
Palmaris longus muscle. Image source: Wikimedia commons<p> We don't have much need these days, at least most of us, to navigate from tree branch to tree branch. Still, about 86 percent of us still have the wrist muscle that used to help us do it. To see if you have it, place the back of you hand on a flat surface and touch your thumb to your pinkie. If you have a muscle that becomes visible in your wrist, that's the palmaris longus. If you don't, consider yourself more evolved (just joking).</p>
Darwin's tubercle<img class="rm-lazyloadable-image rm-shortcode" type="lazy-image" data-runner-src="https://assets.rebelmouse.io/eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpbWFnZSI6Imh0dHBzOi8vYXNzZXRzLnJibC5tcy8xOTA5NjgxMi9vcmlnaW4uanBnIiwiZXhwaXJlc19hdCI6MTY0ODUyNjA1MX0.8RuU-OSRf92wQpaPPJtvFreOVvicEwn39_jnbegiUOk/img.jpg?width=980" id="687a0" width="819" height="1072" data-rm-shortcode-id="ff5edf0a698e0681d11efde1d7872958" data-rm-shortcode-name="rebelmouse-image" />
Darwin's tubercle. Image source: Wikimedia commons<p> Yes, maybe the shell of you ear does feel like a dried apricot. Maybe not. But there's a ridge in that swirly structure that's a muscle which allowed us, at one point, to move our ears in the direction of interesting sounds. These days, we just turn our heads, but there it is.</p>
Goosebumps<img class="rm-lazyloadable-image rm-shortcode" type="lazy-image" data-runner-src="https://assets.rebelmouse.io/eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpbWFnZSI6Imh0dHBzOi8vYXNzZXRzLnJibC5tcy8xOTA5NzMxNC9vcmlnaW4uanBnIiwiZXhwaXJlc19hdCI6MTYyNzEyNTc2Nn0.aVMa5fsKgiabW5vkr7BOvm2pmNKbLJF_50bwvd4aRo4/img.jpg?width=980" id="d8420" width="1440" height="960" data-rm-shortcode-id="8827e55511c8c3aed8c36d21b6541dbd" data-rm-shortcode-name="rebelmouse-image" />
Goosebumps. Photo credit: Tyler Olson via Shutterstock<p>It's not entirely clear what purpose made goosebumps worth retaining evolutionarily, but there are two circumstances in which they appear: fear and cold. For fear, they may have been a way of making body hair stand up so we'd appear larger to predators, much the way a cat's tail puffs up — numerous creatures exaggerate their size when threatened. In the cold, they may have trapped additional heat for warmth.</p>
Tailbone<img class="rm-lazyloadable-image rm-shortcode" type="lazy-image" data-runner-src="https://assets.rebelmouse.io/eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpbWFnZSI6Imh0dHBzOi8vYXNzZXRzLnJibC5tcy8xOTA5NzMxNi9vcmlnaW4uanBnIiwiZXhwaXJlc19hdCI6MTY3MzQwMjc3N30.nBGAfc_O9sgyK_lOUo_MHzP1vK-9kJpohLlj9ax1P8s/img.jpg?width=980" id="9a2f6" width="1440" height="1440" data-rm-shortcode-id="4fe28368d2ed6a91a4c928d4254cc02a" data-rm-shortcode-name="rebelmouse-image" />
Image source: Decade3d-anatomy online via Shutterstock<p>Way back, we had tails that probably helped us balance upright, and was useful moving through trees. We still have the stump of one when we're embryos, from 4–6 weeks, and then the body mostly dissolves it during Weeks 6–8. What's left is the coccyx.</p>
The palmar grasp reflex<img class="rm-lazyloadable-image rm-shortcode" type="lazy-image" data-runner-src="https://assets.rebelmouse.io/eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpbWFnZSI6Imh0dHBzOi8vYXNzZXRzLnJibC5tcy8xOTA5NzMyMC9vcmlnaW4uanBnIiwiZXhwaXJlc19hdCI6MTYzNjY0MDY5NX0.OSwReKLmNZkbAS12-AvRaxgCM7zyukjQUaG4vmhxTtM/img.jpg?width=980" id="8804c" width="1440" height="960" data-rm-shortcode-id="67542ee1c5a85807b0a7e63399e44575" data-rm-shortcode-name="rebelmouse-image" />
Palmar reflex activated! Photo credit: Raul Luna on Flickr<p> You've probably seen how non-human primate babies grab onto their parents' hands to be carried around. We used to do this, too. So still, if you touch your finger to a baby's palm, or if you touch the sole of their foot, the palmar grasp reflex will cause the hand or foot to try and close around your finger.</p>
Other people's suggestions<p>Amir's followers dove right in, offering both cool and questionable additions to her list. </p>
Fangs?<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr">Lower mouth plate behind your teeth. Some have protruding bone under the skin which is a throw back to large fangs. Almost like an upsidedown Sabre Tooth.</p>— neil crud (@neilcrud66) <a href="https://twitter.com/neilcrud66/status/1085606005000601600?ref_src=twsrc%5Etfw">January 16, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
Hiccups<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr">Sure: <a href="https://t.co/DjMZB1XidG">https://t.co/DjMZB1XidG</a></p>— Stephen Roughley (@SteBobRoughley) <a href="https://twitter.com/SteBobRoughley/status/1085529239556968448?ref_src=twsrc%5Etfw">January 16, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
Hypnic jerk as you fall asleep<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr">What about when you “jump” just as you’re drifting off to sleep, I heard that was a reflex to prevent falling from heights.</p>— Bann face (@thebanns) <a href="https://twitter.com/thebanns/status/1085554171879788545?ref_src=twsrc%5Etfw">January 16, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script> <p> This thing, often called the "alpha jerk" as you drop into alpha sleep, is properly called the hypnic jerk,. It may actually be a carryover from our arboreal days. The <a href="https://www.livescience.com/39225-why-people-twitch-falling-asleep.html" target="_blank" data-vivaldi-spatnav-clickable="1">hypothesis</a> is that you suddenly jerk awake to avoid falling out of your tree.</p>
Nails screeching on a blackboard response?<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr">Everyone hate the sound of fingernails on a blackboard. It's _speculated_ that this is a vestigial wiring in our head, because the sound is similar to the shrill warning call of a chimp. <a href="https://t.co/ReyZBy6XNN">https://t.co/ReyZBy6XNN</a></p>— Pet Rock (@eclogiter) <a href="https://twitter.com/eclogiter/status/1085587006258888706?ref_src=twsrc%5Etfw">January 16, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
Ear hair<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr">Ok what is Hair in the ears for? I think cuz as we get older it filters out the BS.</p>— Sarah21 (@mimix3) <a href="https://twitter.com/mimix3/status/1085684393593561088?ref_src=twsrc%5Etfw">January 16, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
Nervous laughter<blockquote class="twitter-tweet" data-lang="en"><p lang="en" dir="ltr">You may be onto something. Tooth-bearing with the jaw clenched is generally recognized as a signal of submission or non-threatening in primates. Involuntary smiling or laughing in tense situations might have signaled that you weren’t a threat.</p>— Jager Tusk (@JagerTusk) <a href="https://twitter.com/JagerTusk/status/1085316201104912384?ref_src=twsrc%5Etfw">January 15, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
Um, yipes.<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr">Sometimes it feels like my big toe should be on the side of my foot, was that ever a thing?</p>— B033? K@($ (@whimbrel17) <a href="https://twitter.com/whimbrel17/status/1085559016011563009?ref_src=twsrc%5Etfw">January 16, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
Context is everything.
The COVID-19 pandemic has introduced a number of new behaviours into daily routines, like physical distancing, mask-wearing and hand sanitizing. Meanwhile, many old behaviours such as attending events, eating out and seeing friends have been put on hold.
A new study looks at how images of coffee's origins affect the perception of its premiumness and quality.
- Images can affect how people perceive the quality of a product.
- In a new study, researchers show using virtual reality that images of farms positively influence the subjects' experience of coffee.
- The results provide insights on the psychology and power of marketing.