P just means that a deterministic Turing machine can solve it in a \(\bf P\)olynomial number of steps.
NP means a \(\bf N\)on-deterministic Turing machine can solve it in a \(\bf P\)olynomial number of steps.
A Turing machine is an infinitely long band of tape and a cursor with a counter. The tape consists of frames and each frame has a symbol. The symbol gives the cursor an instruction, such as move left or right, change the counter value, and write a symbol down on another frame. A deterministic Turing machine has at most one instruction in each frame, while a non-deterministic Turing machine can have multiple instructions in each frame. When the cursor hits a frame with \(n\) instructions, then it splits into \(n\) different cursors and they run each instruction independently of each other.
You can think of a deterministic Turing machine as our current computers if they were to have infinite memory. When we're talking about these things, generally we're ignoring any limitations in RAM or drive. The main difference between deterministic and non-deterministic is that deterministic must commit to a single choice, while a non-deterministic execute all choices simultaneously to solve a problem.
The both machines have the same computing power, which is to say that if either one of them can solve a computing problem, both of them can. The issue is how many steps it would take to solve the problem. If we try to emulate a non-deterministic Turing machine, we have to keep a collection to hold the positions and counters of each cursor, and we would still have to execute their operations sequentially. It would be exponential increase in the number of steps.
In general, implementing problems on the theoretical Turing machines is a bit difficult, so instead what we tend to do is to use an algorithm to solve another algorithm and vise versa.
For example, the `min` operation gets the smallest element in a collection. The `sort` operation puts all elements in a collection in order. We can utilize `min` to solve `sort` by finding the `min` element, removing it, and putting it into a new sorted collection. We could repeat this until the collection was sorted. We would only need to repeat this process \(n\) times (the size of the collection), which is a polynomial.
Since the composition of a polynomial with a polynomial is still a polynomial, then we know that if `min` is a P problem, then `sort`, which can be solved using `min` a polynomial number of times, must also be a P problem. In fact we would say that `sort` is no harder than `min` in terms of polynomial steps.
We say a problem is NP Hard if it can be used a polynomial number of times to solve any NP problem . Thus we can say that every NP problem is no harder than every NP Hard problem. The 'no harder than' designation can be shown the same way I showed that `sort` is no harder than `min`. Also since it is a transitive relation, we really only have to solve the "hardest" NP problems using the NP Hard problem to show it is NP hard.
The "hardest" NP problems are what we would call NP Complete problems. They are problems which are both NP Hard and NP. Suppose problem \(A\) is NP, and you're not sure about problem \(B\). If you can show that \(A\) is no harder than \(B\), then you know \(B\) is NP Hard. If you can show that \(B\) is no harder than \(A\) as well, then you've known that \(B\) is NP. Showing both would mean \(B\) would be NP Complete.
We know NP problems can be used to solve P problems in a polynomial number of steps, which means that P problems are also NP problems.
So far, no one has ever been able to solve an NP Complete problem using any P problem a polynomial number of times. Therefore we don't know if NP Complete is no harder than P or not. If it were true, then that would mean P = NP = NP Complete. All of our current methods for solving NP Complete problems require an exponential number of steps, but if someone showed P = NP they could all be solved in a polynomial number of steps. Breaking encryption is an NP Complete problem.
Just to keep some things in mind:
P is no harder than NP, and P is a subset of NP.
NP is no harder than NP Hard, and NP Complete is a subset of NP and NP Hard.
So far, it seems that NP Complete is harder than P which means P \(\neq\) NP, but it has yet to be proven whether or not P and NP Complete are equivalent (neither is harder than the other).