Here is a largely correct ELI5: P != NP asks the question "Are problems that are easy to verify (NP) also Easy to solve? (P)".

Note that the reverse is obviously true: problems that are easy to solve are also easy to verify.

Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the answer 5 and comparing it with your answer. So we can conclude "Problems that are easy to solve are easy to verify" In other words, P ⊆ NP.

_Now is the reverse true? Are problems that are easy to verify also easy to solve?_

Let me give you an example. Let us assume that the question is "Is 1053188576519689 prime?". You come back and tell me, "No it is not prime, it is divisible by 32,452,867".

1) It is easy to verify your solution. I can divide 1053188576519689 by 32,452,867 and verify that it is indeed divisible. 2) It is hard to solve the problem, I have to try out numbers from 2,3,...,sqrt(1053188576519689), which is quite painful. (Or maybe there is as yet undiscovered better algorithm). So it appears that problems that are easy to verify may not be easy to solve. Or it appears that NP ⊆ P is not true. In other words, it appears P != NP (because if P ⊆ NP and NP ⊆ P, P == NP).

NP problems have wide ranging applications in things like cryptography for example. Let us assume I have a hashing technique. It is easy to hash a document, but hard to reconstruct the document from the hash. Then this technique can be used in auctions where you do not trust the auctioneer. You publicly submit the hash of your bid before the deadline. You do not submit your bid itself, because you are afraid that the person handing out the contracts will reveal the number to his brother-in-law who will bid $1 more than you and win the contract. After the deadline is passed, you send your actual bid to the Auctioneer.

Now 1) Everyone can verify that the documents have not been altered (the hashes are posted publicly, each document can be hashed and compared with its publicly posted hash). So it is easy to verify that the documents have not been tampered with after the deadline.

2) Nobody can construct the document from the hash. So it is not easy to solve for the bid document given the hash. So everyone can post the hash publicly with confidence before the deadline.

If P != NP we can have this type of auctions. If P == NP then there is no difference between posting the hash publicly and posting the document publicly.

user:	teton_ferb
created:	August 11, 2017
karma:	105