Computer Science

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.

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."

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?

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.

Want to dive even further into the world's toughest math problems? Check out "The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles Of Our Time" by Keith J. Devlin. We handpick reading recommendations we think you may like. If you choose to make a purchase, Curiosity will get a share of the sale.

Watch And Learn: Our Favorite Content About Unsolved Problems

Why Is P vs. NP Important?

Written by Joanie Faletto March 7, 2017

Curiosity uses cookies to improve site performance, for analytics and for advertising. By continuing to use our site, you accept our use of cookies, our Privacy Policy and Terms of Use.