Math

The P Versus NP Problem Is One Of Computer Science's Biggest Unsolved Problems

In the world of theoretical computer science, P vs. NP is something of a mythical unicorn. It's become notorious, since it remains an unsolved problem. It basically asks this: If it is easy to check that a solution to a problem is correct, is it also easy to solve that problem? Get back to us when you have an answer.

Related: Grigori Perelman Solved The Poincaré Conjecture-And That Was Enough

Why Is This So Hard?

In the P vs. NP problem, the P stands for polynomial and the NP stands for nondeterministic polynomial time. Did we lose you? Let's back up. In simpler terms, P stands for problems that are easy for computers to solve, and NP stands for problems that are not easy for computers to solve, but are easy for them to check. Here's when an example might be helpful: "A farmer wants to take 100 watermelons of different masses to the market. She needs to pack the watermelons into boxes. Each box can only hold 20 kilograms without breaking. The farmer needs to know if 10 boxes will be enough for her to carry all 100 watermelons to market."

Related: The Goldbach Conjecture Is A Simple Problem That's Never Been Solved

This sample problem is not easy to solve; it requires you to go through every dang possible combination. Checking the final answer, however, is pretty easy. All P problems are also NP problems (if a computer can easily solve it, the computer can also easily check it). The question remains open: Are P problems and NP problems the same type of problem? Or, are there are some problems that are easily verified but not easily solved?

Related: There's A Formula That Gives The First 18 Trillion Trillion Digits Of The Constant e

Who Wants To Be A Millionaire—From Math?

You may be wondering who really cares about this sort of thing. Well, if someone could show that P is equal to NP, it would make difficult real-world problems a piece of cake for computers to solve. Oh, and the person who solves this problem would also get $1 million from the Clay Mathematics Institute. The P vs. NP Problem is one of six unsolved Millennium Problems that hold a million-dollar prize for whoever cracks it.

Is there something you're curious about? Send us a note or email us at editors (at) curiosity.com. And follow Curiosity on Facebook, Instagram and Twitter.

Watch And Learn: Our Favorite Content About Unsolved Problems

Why Is P vs. NP Important?

Share the knowledge!
Written By Curiosity Staff March 7, 2017