P is the set of all problems that can be verified in time polynomial to the problem space. NP is the set of all problems that can be verified in time polynomial to the problem space with the use of a non-deterministic oracle.
Hold that thought.
If you have a list of n elements, you can search through the list and check if an element is in that list in n^1 time. If you have a list of n elements, you can check some property on a triplet of numbers in (at worst) n^3 time, looping once for each member of the triplet.
I can check that there's a triplet that multiplies to 1337 mod 31337, in a set of n numbers, with three nested loops, and doing the modular multiplication in the inner loop, in n^3 time.
Now! What if there were a magic box you could use? Whenever there are three such numbers in the set, it picks them out; whenever there are none, it just finds any three. You can use that magic box, get the three numbers it picks, check it, and voila, you find your answer immediately, in 1 step instead of n^3.
So if a problem is in NP, you need a magic box if the problem is going to be solvable in n^1, n^2, n^3 steps based on n inputs. (They recently showed that Primality-Testing was in P; an n digit number can be factored in n^12 steps. Large, but still polynomial, and better than the exponential-time 2^n.) If a problem is in P, you don't need the magic box to find it in polynomial time.
The magic box is the non-deterministic oracle. The polynomial that expresses how hard the problem is, that's the polynomial of polynomial-time.
You know "https"? The security of "s" is based on how hard it is to factor two large prime numbers multiplied together, and we know it's in NP (just give me the two numbers, and I can check), but we don't think P=NP, ie we don't think there's an easy way to break all online commerce. (See the RSA algorithm.)
Among other things, we've based electronic commerce on the difficulty of factoring large numbers, which is in NP. If P=NP, then lots of people are going to be very surprised
First, thank you for the explanation. However, regarding your quote above, how would electronic commerce change if it was proved that P=NP ? When you say electronic commerce, I think of the process of buying and selling goods. Are you speaking of the analysis of that process?
If P=NP, then conventional cryptography would be impossible. In particular you would have no public key cryptography so it would not be possible to transmit information securely over an unsecure channel without sharing a some sort of key beforehand. Think of what this will do to online transactions which rely on information like credit card numbers being transmitted securely. I'm sure other areas of the economy would be vastly affected too.
The one form of cryptography that would still be possible is quantum cryptography. But if I recall correctly, that requires that two parties already hold some shared secret before communicating.
Edit: In addition although it would be possible to detect if someone is eavesdropping over your communication, you still wouldn't have the privilege of being able to communicate securely regardless of whether your message is being recorded.
This of course presumes that not only P=NP, but an efficient polynomial time algorithm exists for NP problems i.e. one which is say linear or quadratic or even cubic time.
P=NP in a completely real world intractable way. And if P=NP, one would guess it would be in such an intractible fashion, since otherwise the algorithm would have found it's way into nature or something.
Most researcher think P!=NP to begin with, so if it was proven, very little would change. So it's likely any proof regarding P and NP will have little direct impact, though it might have a big impact just by the mathematical formalism it creates.
Hold that thought.
If you have a list of n elements, you can search through the list and check if an element is in that list in n^1 time. If you have a list of n elements, you can check some property on a triplet of numbers in (at worst) n^3 time, looping once for each member of the triplet.
I can check that there's a triplet that multiplies to 1337 mod 31337, in a set of n numbers, with three nested loops, and doing the modular multiplication in the inner loop, in n^3 time.
Now! What if there were a magic box you could use? Whenever there are three such numbers in the set, it picks them out; whenever there are none, it just finds any three. You can use that magic box, get the three numbers it picks, check it, and voila, you find your answer immediately, in 1 step instead of n^3.
So if a problem is in NP, you need a magic box if the problem is going to be solvable in n^1, n^2, n^3 steps based on n inputs. (They recently showed that Primality-Testing was in P; an n digit number can be factored in n^12 steps. Large, but still polynomial, and better than the exponential-time 2^n.) If a problem is in P, you don't need the magic box to find it in polynomial time.
The magic box is the non-deterministic oracle. The polynomial that expresses how hard the problem is, that's the polynomial of polynomial-time.
You know "https"? The security of "s" is based on how hard it is to factor two large prime numbers multiplied together, and we know it's in NP (just give me the two numbers, and I can check), but we don't think P=NP, ie we don't think there's an easy way to break all online commerce. (See the RSA algorithm.)