Disclaimer: I am currently a student in a Data Science bootcamp, and we have not gotten into algorithms yet. This is just something I stumbled upon while doing some research on my own time. Thought it was an interesting topic. Definitely NOT a pro or experienced with algorithms at all yet. Hopefully I will be soon.
From just my basic understanding, I believe these terms all deal with Big-O notation for algorithms. Hopefully, I can cover this in a very understandable way.
Brief summary, Big-O is a measure of how quickly an algorithm runs or solves a problem (note it is the upper bound of how long the run time is).
P, NP, NP-Hard and NP-Complete are classes that any problem would fall under or would be classified as.
P (Polynomial) problems
P problems refer to problems where an algorithm would take a polynomial amount of time to solve, or where Big-O is a polynomial (i.e. O(1), O(n), O(n²), etc). These are problems that would be considered ‘easy’ to solve, and thus do not generally have immense run times.
NP (Non-deterministic Polynomial) Problems
NP problems were a little harder for me to understand, but I think this is what they are. In terms of solving a NP problem, the run-time would not be polynomial. It would be something like O(n!) or something much larger. However, this class of problems can be given a specific solution, and checking the solution would have a polynomial run-time. An example that helped me understand this a little better was a Sudoku game.
In order to solve this entire puzzle, the algorithm would have to check each 3x3 matrix to see which numbers are missing, then each row, then each column, and then make sure there are no repetitions of any digit from 0–9. This becomes more complex because the number of digits that are missing is inconsistent in each row, column, and matrix (i.e. top-left matrix is missing 4 digits while top-right matrix is missing 8 digits). Solving this problem would not have a polynomial run-time. However, if you were to feed this puzzle with a possible solution, it would be much less complex to check if there are any repetitions in the rows, columns and matrices. This is a simple check which would have a polynomial run-time.
In essence, NP class problems don’t have a polynomial run-time to solve, but have a polynomial run-time to verify solutions (difficult to solve, easy to check a given answer).
Reduction
I can’t really explain this one outside of using examples, so: we have two problems, A and B, and we know problem B is a P class problem. If problem A can be reduced, or converted to problem B, and this reduction takes a polynomial amount of time, then we can say that A is also a P class problem (A is reducible to B).
This concept is important to understand for the other two classes of problems.
NP-Hard Problems
A problem is classified as NP-Hard when an algorithm for solving it can be translated to solve any NP problem. Then we can say, this problem is at least as hard as any NP problem, but it could be much harder or more complex.
NP-Complete Problems
NP-Complete problems are problems that live in both the NP and NP-Hard classes. This means that NP-Complete problems can be verified in polynomial time and that any NP problem can be reduced to this problem in polynomial time.
Below is a venn diagram of the different class spaces.
Hopefully, this could have cleared things up about this topic. Obviously, I have very limited knowledge. I just thought this was interesting to talk about and it seems like, even at a high level, this is pretty confusing.
Some GREAT learning sources I used for this blog:
