Question

P vs. NP explain to me, but in a way a dense person could comprehend it.

Wikipedia is too complex, and after some research into finding simpler explanations, most of them dumb it down too much.

So I guess I am looking for help understanding:

What exactly P vs. NP is?

Why is P vs. NP important to computer science theory or computer science in general?

Optional: Explain the notation or terminology the P vs. NP Wikipedia article uses.

Answer 1

Well, it is importnt cause it is a million bucks! =P

http://www.technologyreview.com/news/420290/what-does-p-vs-np-mean-for-the-rest-of-us/

Or well, because it it what can and can't be done.

Answer 2

P is a class representing all problems that are SOLVABLE in polynomial time. In other words problems which the time solve is equal to some polynomial. Ex. \[x^n\] n is some constant and x is the problem size.

In similar fashion the NP class represents all problems which you can VERIFY i polynomial time.

Now why is it so important to prove that \[P = NP \space or \space P \neq NP\]?

A good example can be found in RSA encryption.
In the inner mechanics of RSA you have to choose two prime numbers p and q which are multiplied to create a number n=pq and a number m=(p-1)(q-1). n and m are then used together to create two new numbers called e and d.

To encrypt we need: a massage, n, and e.
To decrypt we need: a encrypted message, n, and d.

If I want you to send me encrypted messages I would send you my n and my e (public key) and you could use them to encrypt messages only I can decrypt.

Now if some else got hold of the n while I send it to you, they still wouldn't be able decrypt the message because they need the d (private key) which is computed using m.

m is created using p and q and if you can easily factorize n to find p and q then our RSA wouldn't be particularly safe. But this isn't the case.

With todays known (non quantum) algorithms it isn't possible to factorize a number (n in this example) to it's prime components within polynomial time. Which means that it will take \[n^x\]time instead (which is vastly grater than x^n).

If you however already have p and q available it is very simple to prove that n=pq (all you have to do is multiply p and q).

Now if P = NP this implies that there MUST be an algorithm that can factorize large numbers in polynomial time (we just haven't found it yet) and thus it would be very simple to crack in this case the RSA crypto and would practically render internet security useless.

If \[P \neq NP\] then we know that RSA is safe and that the internet is a bit less unsafe (for now :P ).

A proof regardless of outcome does in both cases have lot's of other practical and scientific implications/uses, and it would be incredibly good to know if they are usable. Although I think that most mathematicians would like the the outcome to be P=NP because it's simply more intreseting.


Hope it helped :)
~Lyare

ps. If someone finds an error please let me know and I'll edit the answer.

Answer 3

Correction:
"With todays known (non quantum) algorithms it isn't possible to factorize a number (n in this example) to it's prime components within polynomial time. Which means that it will take n^x time instead (which is vastly grater than x^n)."

should be:
With todays known (non quantum) algorithms it isn't possible to factorize a number (n in this example) to it's prime components within polynomial time. A large p and q implies a very large n which is very difficult to factorize and thus the safty of the RSA is guaranteed. The time it takes to factorize a number is exponential and varies depending on implenetation but is basically \[e^{nx}\] (which is vastly grater than x^n).

Answer 4

I deeply grateful for your explanation @Lyrae the RSA bit was an extremely good example!

Answer 5

I gave a bit more in depth explanation of P and NP here:
http://openstudy.com/study#/updates/556aba1ee4b050a18e838710