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. (http://www.claymath.org/millennium-problems)

Why Is This So Hard?

In the P vs. NP problem (http://news.mit.edu/2009/explainer-pnp), 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.” (https://simple.wikipedia.org/wiki/P_versus_NP)


Behnam Esfahbod / WIkipedia ()

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:
Why is P vs NP Important?

In this video,He explain perhaps the most famous problem in all of Computer Science. Does P = NP? He define the terms and give examples of each. We also programmatically go through the traveling salesman problem. He experiment with a little bit of mixed reality in this video as well.


Sources and References:https://curiosity.com/topics/the-p-versus-np-problem-is-one-of-computer-sciences-biggest-unsolved-problems-curiosity/
https://madatgravity96.wordpress.com/
http://www.claymath.org/millennium-problems

Blog:
https://thegeekiestone.com/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s