P=NP explained, that is interesting as fuck

The core concept is that mathematical problems have varying degrees of difficulty. Some of them can be solved relatively quickly with a computer (P) and some of them take a very long time to solve with a computer (NP). Where it gets interesting is that if you have a solution to an NP problem, it's easy to verify whether or not the solution is correct (if you want to be pedantic, verifying a solution to an NP problem is a P problem).

For example, if I asked you to name a word that is a palindrome and describes a type of boat, you might have to think very hard about it. You might research it on wikipedia or look up "boat" in a thesaurus to try to figure it out, it's going to take a while. So it's an NP problem. But when I tell you that the answer is "kayak", you can look at it and pretty much instantly know that it's correct, right?

The debate is whether or not all problems that can be verified relatively quickly are possible to also solve relatively quickly. There are lots of NP problems that have proven to actually be P, so what if all NP problems are actually P problems that we haven't unraveled yet?

If you could prove that P = NP, e.g. all problems that can be verified easily can also be solved easily, then we would know that there are some amazing problems that are possible to fix (fast protein folding) and also that we have some big problems in our hands (all encryption is possible to circumvent). It would immediately trigger huge investment in all of these areas as there would be proof that there are massive rewards waiting to be discovered.

Where the distinction between P and NP are especially relevant to you every day right now is encryption, making sure that people don't steal your bank passwords and such. The core concept behind encryption is that if you have the right keys to decrypt something, doing so is P. If you don't have the right keys to decrypt it, doing so is NP (at least as far as we know today). When you type your bank password into your web browser, it's sent encrypted over to the bank's web server. Since the bank has the right keys, it can damn-near-instantly decrypt the payload and verify that you typed the right password. But if nefarious people have compromised your internet connection and intercepted your encrypted password, it doesn't do them any good because without the right keys it would take massive amounts of time to decrypt it - with modern computers and the right algorithms, we're literally talking about billions of years. So if someone proved that P = NP, we're in deep shit because that means there's a way to steal all encrypted data on the internet, we just haven't figured it out yet. But, it also means there's probably a cure for cancer.

/r/videos Thread Parent Link - youtube.com